𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Combinatorial Properties and the Complexity of a Max-cut Approximation

✍ Scribed by Charles Delorme; Svatopluk Poljak

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
667 KB
Volume
14
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We study various properties of an eigenvalue upper bound on the max-cut problem. We show that the bound behaves in a manner similar to the max-cut for the operations of switching, vertex splitting, contraction and decomposition. It can also be adjusted for branch and bound techniques. We introduce a Gram representation of a weighted graph, in order to construct weighted graphs with pre-given eigenvalue properties. As a corollary, we prove that the decision problem as to whether the upper bound coincides with the actual value of the max-cut is (N P)-complete. We study the mutual relation between the max-cut and the bound on the line graphs, which allow a good approximation. We show that the ratio between the upper bound and the actual size of the max-cut is close to (9 / 8) for the studied classes, and for several other graphs.

πŸ“œ SIMILAR VOLUMES

A Short Proof of Seymour's Characterizat
A Short Proof of Seymour's Characterization of the Matroids with the Max-Flow Min-Cut Property
✍ Bertrand Guenin πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 113 KB

Seymour proved that the set of odd circuits of a signed binary matroid ðM; SÞ has the Max-Flow Min-Cut property if and only if it does not contain a minor isomorphic to ðMðK 4 Þ; EðK 4 ÞÞ: We give a shorter proof of this result. # 2002 Elsevier Science (USA)