Detecting the solution space of vertex cover by mutual determinations and backbones

Area of Science:

• Theoretical Computer Science
• Graph Theory
• Combinatorial Optimization

Background:

• Solving combinatorial optimization problems, particularly the minimal Vertex-cover problem, is crucial for efficiency in computer science and related fields.
• Understanding the solution space of Vertex-cover is a key challenge.

Purpose of the Study:

• To introduce a novel structure, mutual-determination, for analyzing Vertex-cover on general graphs.
• To develop an efficient algorithm for exploring the solution space of Vertex-cover.

Main Methods:

• Definition and discovery of the mutual-determination structure.
• Utilizing backbones and mutual-determinations with node ranks derived from leaf removal.
• Proposing the Mutual-determination and Backbone Evolution Algorithm to generate a reduced solution graph.

Main Results:

• The algorithm provides a graphical representation of the Vertex-cover solution space.
• It enables strict acquisition of the entire solution space and detailed structures like backbones when no leaf-removal core exists.
• Performance is comparable to replica symmetry algorithms, with a small gap to replica symmetric breaking, and exhibits low error for exact results.

Conclusions:

• The mutual-determination approach offers a new perspective for solving Vertex-cover and understanding solution space organization.
• The reduced solution graph serves as an alternative method for analyzing ground/steady states.