Berlin 2012 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 31: Phase Transitions and Critical Phenomena
DY 31.10: Talk
Friday, March 30, 2012, 12:15–12:30, MA 004
Improved Linear Programming applied to the Vertex Cover Problem — •Timo Dewenter and Alexander K. Hartmann — Institut für Physik, Universität Oldenburg, 26111 Oldenburg
We consider the well studied [1] NP-complete Vertex Cover problem (VC) on Erdős-Rényi (ER) random graphs with finite connectivity c.
Previously, we applied the mapping of VC to a Linear Programming problem (LP), where the nodes of the graph are represented by real-valued variables xi ∈ [0,1]. A value of xi = 0 means that the node is uncovered and xi = 1 denotes a covered node. Each edge {j,k} in the graph is related to a constraint xj + xk ≥ 1 in the LP. The Simplex-algorithm is then applied to solve this LP, but for larger c incomplete solutions with variables xi ∈ ]0,1[ are found. So we used a cutting-plane approach that adds constraints to the LP based on loops in the graph with odd length leading typically to exact solutions for c < e ≈ 2.718.
Here, we solve small subgraphs GS =(U,EU) with an exact algorithm and add contraints ∑xi ∈ U ≥ |VC(GS)| to the LP, where |VC(GS)| is the size of the minimum VC of GS. This leads in principle to complete solutions, but here we only use |U| ≤ 10. The behaviour of this algorithm is studied for ER random graphs as a function of c. After performing statistical analyses [2] for different system sizes, we compare with the phase diagram for the critical fraction xc of covered vertices.
M. Weigt and A.K. Hartmann, Phys. Rev. Lett. 84, 26 (2000)
A.K. Hartmann: Practical Guide to Computer Simulations, World-Scientific, 2009