Determining the Solution Space of Vertex-Cover by Interactions and Backbones
arXiv:1112.6079 · doi:10.1103/PhysRevE.86.016112
Abstract
To solve the combinatorial optimization problems especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects. Aiming at detecting the solution space of Vertex-cover, a new structure named interaction between nodes is defined and discovered for random graph, which results in the emergence of the frustration and long-range correlation phenomenon. Based on the backbones and interactions with a node adding process, we propose an Interaction and Backbone Evolution Algorithm to achieve the reduced solution graph, which has a direct correspondence to the solution space of Vertex-cover. By this algorithm, the whole solution space can be obtained strictly when there is no leaf-removal core on the graph and the odd cycles of unfrozen nodes bring great obstacles to its efficiency. Besides, this algorithm possesses favorable exactness and has good performance on random instances even with high average degrees. The interaction with the algorithm provides a new viewpoint to solve Vertex-cover, which will have a wide range of applications to different types of graphs, better usage of which can lower the computational complexity for solving Vertex-cover.
References in corpus (13)
- Understanding individual human mobility patterns
- Statistical Mechanics of Community Detection
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Giant strongly connected component of directed networks
- Clustering of solutions in the random satisfiability problem
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Core percolation in random graphs: a critical phenomena analysis
- Immunization of Real Complex Communication Networks
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Message passing for vertex covers
- Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
Cited by in corpus (5)
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
- The network source location problem: ground state energy, entropy and effects of freezing
- Organization mechanism and counting algorithm on Vertex-Cover solutions
- Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking