--

We are looking for a cycle, the edge weights of which sums to zero. So does this map to the presence of a cycle in the new model?

A simple example with 2 vertices and anti-parallel edges of weights (1,-1) and (-1,1) shows a cycle in the new graph. What does this mean?

Are we asking for an APSP in hypergraphs?

We are looking at a type of graphs called directed hypergraphs. Call them DHG. How is a DHG represented? Show figures of the representation.

Found the tutorial paper.

--

Does this mapping from PRDG to DHG map to detection of cycles in the new graph?

Define a path and cycle. B-arc, F-arc.

We can do a DFS and assign to each vertex a DFS number.

--

**To do:**make examples and check them, especially the ones similar to KMW.

What does MDS mean? coloring?

--

Call as fictitious nodes, nodes that correspond to the bottom part of the block matrix. Cycles which involve the fictitious nodes donot seem to matter. Classify this statement.

**Statement of the zero cycle detection:**begin at an "actual" node and do a DFS. If we reach a node back, then we get to a cycle. Is this right?

--

**To do**: read how does a DFS detects cycles: types of edges: tree edges, back edges, cross edges and forward edges.

--

did some part of DV-KMW-EX.

A "ZC" should touch both the original vertices and also the new vertices.

Partition the nodes into actual nodes and dist-nodes (call them D-nodes). A ZC in the PRDG should touch both nodes and D-nodes.

--

Group the nodes into the G-nodes and D-nodes. If there exists a cycle which has at least one node from G-set and atleast one node from D-set, then we have a zero-cycle in the original PRDG. Mark a hyperedge e (u_1...u_i -> v_1...v_j) as dashed if u_k (k \in 1..i) \in G-set and v_l (l \in 1...j) \in D-set. Or otherwise.

Look up the definition of Hypergraph from here. Also, get the definition of dual of a hypergraph, among other definitions.

This is a restatement of the Farkas lemma.

--

Modular Memory allocation: fibonacci example.