Presence of multi-dimensional schedules in a graph theoretic way

Suppose we assume that Bx <> 0
This can be written as two inequalities

Bx >= 1

Bx <= -1

We can search for a vector x that satisfies these constraints using a graph-theoretic fashion.
Hints:

look up the max-flow min-cut proof for TUM.

how did Tarjan solve the problem?

How can this problem be solved in that way?

What does multi-dimensional schedules mean in a graph theoretic way?

Note: Interval graphs are duals of directed graphs. If we transpose the incidence matrix of a directed graph, we obtain a interval graph. Correction: We obtain a interval matrix, not a interval graph. Question: how are interval matrices and interval graphs related?

Things to do
-----------
read the max-flow min-cut from the lecture notes
read the same from Schrijver
read the same from Cook
The theorem essentially uses the fact that if a graph is directed, its incidence matrix is TUM
It can also be checked for TUMity in polynomial time
--

read about network matrices from all three sources
how are network matrices different from directed graphs

some terminology
Weakly connected digraph: if the underlying directed graph is connected
------------------
interval graphs idea
--
read about network matrices from all three sources
interval graphs idea
exercises from lecture notes and cook..
---------------
NOTES from Golumbic:
interval graphs lead to PQ trees => how does that help?
----------------
Interval graphs Vs. interval matrices: What is the difference?
----------------

TUMity is a hereditary property.

Goldberg and Sailesh Rao have an extremely fast algorithm in a graph theoretic way for the max-flow problem. Have a look at it. This is the link.

-----------
A simple proof:
STMT1: TUMity of the directed graph to proof of KMW: This is in the spirit of the max-flow min-cut proof.
statement of KMW: either there exists a null-weight cycle or there exists a (possibly multi-dim-time) schedule
STMT2: Decompose the input PRDG into one whose dependences can lead to a TUM matrix. Use the equivalent of Menger's theorem for getting possibly faster schedules possibly in a better runninhg time