maximal independent subspaces

The main idea of CM-Z is finding maximal independent subspaces (1) without using a LP formulation and (2) in a fast way.
The scheduling matrix is not the same for all the variables if the depth of the decompoisition tree is > 1.
Maybe looking at the following problem would help? How to do fastly, all-pair shortest paths when the weights of the graphs are in the from {-1,0,+1}. maybe looking at Tarjan's result on max-flow under such weights would help?
Problem: You are given a set of variables, with linear constraints between them. You may not have constraints between every pair of variables. However, there are no "unconnected or lonely" variables, as they can be easily removed using a SCC algorithm. How fast can you check if a solution exists for them? or, how fast can you compute a hyperplane that can separate the variables in one shot, if ever you can do it?
--
there are two problems here:

sub-problem1 is to do a fast null cycle detection when the depth of the decomposition tree is known (in particular when it is 1)

subproblem2 is to do the same when the components of the weights are in a known range, in particular, when they are from {-1,0,+1}
--
Look up the definition of P-Complete and NC.