Books and some notes

These are some books

Golumbic's book or Shamir's notes

Schrijver's any of three books: Schrijver1984, Cook... Schrijver, Schrijver2004

Schrijver's lecture notes

Cornuejols's book

An interval graph is perfect. Its interference graph

has consecutive 1's property.

is TUM

--
the reduction to SAT of the simple cycle problem seems to be easy, look at the standard reduction of ILP to SAT.
--
This zero weight cycle problem is something like two flow algorithms running in parallel to each other, checking if the value of one is equal to the other: resulting in a null-weight cycle.
--
more importantly, what can be done when the weights belong to 0, \pm 1??????
gcd?? I meant "any ideas":)
--
Check out linear programming when

dimension is small

when the weights are small: unit distances, in particular

Ckeck out the polynomial time linear programming algorithms (Khachiyan-Karmarkar-Karp) from Schrijver and also from Chong. Also, Meggido's algorithm for fixed dimensions
--
This seems to be a nice pecking order:

linear programming is a black-box-tool that solves all linear problems in polyhedral model, reasonably, with simplex or other ways

a smaller problem is scheduling in polyhedral model: till now uses LP: what next?

max-flow could also use LP, because of known reasons (TUMity, duality property, etc...). We can crank up the blocking flow enough number of times to obtain a near quadratic algorithm.