Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem

Abstract

The phase-transition behavior of the NP-hard vertex-cover (VC) combinatorial optimization problem is studied numerically by linear programming (LP) on ensembles of random graphs. As the basic Simplex (SX) algorithm suitable for such LPs may produce incomplete solutions for sufficiently complex graphs, the application of cutting-plane (CP) methods is sought. We consider Gomory and {0,1/2} cuts. We measure the probability of obtaining complete solutions with these approaches as a function of the average node degree c and observe transition between typically complete and incomplete phase regions. While not generally complete solutions are obtained for graphs of arbitrarily high complexity, the CP approaches still advance the boundary in comparison to the pure SX algorithm, beyond the known replica-symmetry breaking (RSB) transition at c=e=2.718... . In fact, our results provide evidence for another algorithmic transition at c=2.90(2). Besides this, we quantify the transition between easy and hard solvability of the VC problem also in terms of numerical effort. Further we study the so-called whitening of the solution, which is a measure for the degree of freedom that single vertices experience with respect to degenerate solutions. Inspection of the quantities related to clusters of white vertices reveals that whitening is affected, only slightly but measurably, by the RSB transition.

arXiv comment14 pages, 9 figures

References in corpus (21)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Survey Propagation as local equilibrium equations
• Core percolation in random graphs: a critical phenomena analysis
• Focused Local Search for Random 3-Satisfiability
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Circumspect descent prevails in solving random constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Computational complexity arising from degree correlations in networks
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Phase coexistence and finite-size scaling in random combinatorial problems
• Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Clustering analysis of the ground-state structure of the vertex-cover problem
• The large deviations of the whitening process in random constraint satisfaction problems
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Phase transition for cutting-plane approach to vertex-cover problem
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Optimal Vertex Cover for the Small-World Hanoi Networks