Partition Independent Set and Reduction-Based Approach for Partition Coloring Problem.

Area of Science:

• Graph Theory
• Combinatorial Optimization
• Computer Science

Background:

• The partition coloring problem (PCP) involves selecting one vertex per partition to minimize the chromatic number of the induced subgraph.
• PCP is crucial for optical network routing and wavelength assignment, constraint encoding, and scheduling.
• Solving PCP for large graphs is challenging due to its NP-complete nature.

Purpose of the Study:

• To develop an efficient algorithm for solving the partition coloring problem (PCP).
• To introduce novel concepts and techniques for improving PCP solution efficiency and quality.

Main Methods:

• Proposed a partition independent set (PIS) concept and developed the FastPIS algorithm to find a maximum PIS.
• Introduced an l-clustering-degree bound ordered set (l-CDBOS) for graph reduction.
• Developed the HotPGC algorithm integrating FastPIS and l-CDBOS for solving PCP.

Main Results:

• HotPGC provides high-quality initial solutions for PCP.
• The l-CDBOS reduction rule effectively reduces the working graph scale.
• Evaluations on benchmark graphs show HotPGC achieves competitive performance against state-of-the-art algorithms.

Conclusions:

• HotPGC is an efficient and effective method for solving the partition coloring problem.
• The novel concepts of PIS and l-CDBOS significantly contribute to the algorithm's performance.
• The study advances the state-of-the-art in solving NP-complete graph problems with practical applications.