Iterated Clique Reductions in Vertex Weighted Coloring for Large Sparse Graphs.

Area of Science:

• Graph Theory
• Combinatorial Optimization
• Computer Science

Background:

• The Minimum Vertex Coloring (MinVC) problem, a fundamental NP-hard problem, seeks to minimize colors for adjacent vertices.
• The Minimum Vertex Weighted Coloring (MinVWC) problem generalizes MinVC by assigning weights to vertices and minimizing the total weight of colors used.

Purpose of the Study:

• To develop an effective reduction algorithm for the NP-hard Minimum Vertex Weighted Coloring (MinVWC) problem.
• To improve upon existing methods by creating smaller subgraphs for efficient problem-solving.

Main Methods:

• Proposed a novel reduction algorithm based on maximal clique enumeration.
• The algorithm employs clique sampling and graph reductions, including promising clique reductions, better bound reductions, and post reductions.
• It leverages lower bounds derived from a proportion of maximal cliques to guide the reduction process.

Main Results:

• Experimental results demonstrate that the proposed algorithm generates considerably smaller subgraphs compared to the state-of-the-art RedLS method on large benchmark graphs.
• Individual impacts and practical properties of the algorithm's components were evaluated.
• A theoretical result shows the algorithm's reduction effects are equivalent to exhaustive maximal clique enumeration given sufficient runtime.

Conclusions:

• The developed maximal clique enumeration-based reduction algorithm is highly effective for the MinVWC problem.
• It offers a significant improvement in subgraph reduction, outperforming recent methods.
• The algorithm provides a theoretically sound and practically efficient approach to tackling complex graph coloring problems.