Phase transition for cutting-plane approach to vertex-cover problem

Abstract

We study the vertex-cover problem which is an NP-hard optimization problem and a prototypical model exhibiting phase transitions on random graphs, e.g., Erdoes-Renyi (ER) random graphs. These phase transitions coincide with changes of the solution space structure, e.g, for the ER ensemble at connectivity c=e=2.7183 from replica symmetric to replica-symmetry broken. For the vertex-cover problem, also the typical complexity of exact branch-and-bound algorithms, which proceed by exploring the landscape of feasible configurations, change close to this phase transition from "easy" to "hard". In this work, we consider an algorithm which has a completely different strategy: The problem is mapped onto a linear programming problem augmented by a cutting-plane approach, hence the algorithm operates in a space OUTSIDE the space of feasible configurations until the final step, where a solution is found. Here we show that this type of algorithm also exhibits an "easy-hard" transition around c=e, which strongly indicates that the typical hardness of a problem is fundamental to the problem and not due to a specific representation of the problem.

4 pages, 3 figures

References in corpus (2)

• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• Clustering analysis of the ground-state structure of the vertex-cover problem

Cited by in corpus (10)

• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Typical Approximation Performance for Maximum Coverage Problem
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem