Title :
Odd-cycle inequalities, via minimization and LP-completeness
Author_Institution :
Dept. of Phys. & Comput., Wilfrid Laurier Univ., Waterloo, Ont., Canada
Abstract :
We report solving odd-cycle inequalities linear programs to obtain Max-Cuts of instances of planar graphs obtained from the via minimization of the circuit layer assignment problem (where electrically common points have degree of at most three) in running times comparable to well-known fast approximate methods. This method does not require graph embeddings in the plane or graph transformations and runs in polynomial time. Furthermore, this odd-cycle LP relaxation of the Max-Cut problem on general graphs is proved to be as intractable as any other Max-Cut LP relaxation with respect to the question of being able to recognize exactly those problem inputs which have a 0-1 optimal solution to the linear program. This serves to strengthen the argument for attempting to solve non-planar Max-Cut problems by solving for the odd-cycle LP relaxation
Keywords :
circuit layout; graph theory; linear programming; minimisation; LP-completeness; circuit layer assignment problem; max-cut LP relaxation; nonplanar max-cut problems; odd-cycle inequalities linear programs; planar graphs; polynomial time; via minimization; Circuits; Linear programming; Minimization methods; Physics computing; Polynomials; Tree graphs; Wires;
Conference_Titel :
Circuits and Systems, 1993., Proceedings of the 36th Midwest Symposium on
Conference_Location :
Detroit, MI
Print_ISBN :
0-7803-1760-2
DOI :
10.1109/MWSCAS.1993.343096