Some notes on KMW and unitary graphs

Problems to solve on unitary graphs (directed graphs whose edges are annotated by d-dimensional weights each component of which is from the set {0,+1,-1})

Is the graph computable (does it have a null weight cycle which is not necessarily simple)?

If so, what is the (minimum) dimension of the schedule it allows?

memory optimization1: given a schedule, give a optimal memory allocation for it.

memory optimization2: find the schedule and allocation together, optimally.

--
multi-dim schedules may not be feasible for imperative programs is this right? check up the meaning of multi-dim schedules. look at the example in DV-KMW paper. The example gives a 2-dim schedule for a program in a imperative way.

Assume that the unitary-SURE is computable and that a 1-dim schedule exists. It means that, no null-weight cycle exists and the depth of the decomposition algorithm is 1. So, after one run of the KMW-decomposition algorithm, all the vertices are separated.
having a null-weight cycle is a heriditary property
--
This means that no edge casts a shadow on the another edge => the dot products of any edge weight with any other edge weight is 0???????????????????????
This means that if we (could) enumerate all the self loops to a vertex, the weight of the path is non zero (= condition of no null-weight-cycle). It also means that the weight of two paths that donot touch each other (no common vertex other than itselof) donot combine to zero (can we remove such paths through a initial run of SCC?)
WHAT DOES all the vertices separating in one shot mean?
THINGS TO DO: look closely at the LP programs that they propose. Especially, the variables v and q.
--
q_e is non-zero, v_e is zero on the selected edges. What does that give us?
--
the depth of the decomposition algorithm gives the dimensionality of the schedule. Further, one-dimensional schedules are better than 2-dimensional schedules are better than 3-dimensional schedules are better than ...... Can this be framed as a edge-coloring problem? Can the edges be colored with 1 color? if not use 2 colors. If not use 3 colors.... Or frame the edges as ones which go away in the first shot of the decomposition algorithm, ones that go away in the second shot of the decomposition algorithm....
--
So, begin with a PRDG and see if allows a 1-dimensional schedule => all edges go away after one shot. do the directions of the edges matter?
--
How can all the edges be put in one coloring class? or what does it mean to separate all the vertices of the graph from each other based on just one run of the decomposition algorithm?
--
Things to do: read Cohen-Megiddo's paper and try to apply it to multi-dimension scheduling.