complexity of KMW aka ZC detection problem

According to Megiddo's 1984 paper, LP is in linear time if the number of constraints is fixed. So, given a (n+d)*m matrix, it is not clear why the algorithm should not be linear if both n and d are fixed or even one of them is fixed. More precisely, if d is fixed, CM-Z give a POLY time algo. What about the case when n is fixed? it is not a POLY time. Is it important? It could be inteersting in cases when n << d.

One difficulty, of course from the fact that the problem has two things (1) A graph defining the dependence directions (2) A set of constraints which define the distances.

Wierd question: Can we make a graph which defines the distances and a set of constraints which define the dependences?
Imagine a network of small nodes (a specific color associated with each nodes of a specific type) with an edge between any two nodes determining the dependence between them.
question: what does it mean when CM-Z say that m = O(n^3) or similar things? Do they mean that the graph is a multi-graph? why not?
--
The main intuition of the Megiddo's 1984 paper on LP is driven by Dantzig's observation: there are many redundant constraints. How can we remove the redundant ones fastly?
--
An oracle gives us the depth of the decomposition tree. Let k be the depth of the decomposition tree. How about making O(log k) queries to the oracle and running a scheduler which could run fast assuming that is the depth of the tree?
--
ala fast mat-mul or gaussian elimination when the depth of the decomposition tree is 1??????
--
Start with an example!!!!!! for 1-d sccheduling and one for unitary problem. The 2 node example of KMW with the self edges removed, has decomposition tree of depth 1. Look up the examples in KMW which are similar to this, and have depth 1.