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

Given a graph whose vertex set is partitioned, the partition coloring problem (PCP) requires the selection of one vertex from each partite set, such that the subgraph induced by the set of the selected vertices has the minimum chromatic number. Motivated by the routing and wavelength assignment problem for optical networks, PCP has been used to model many other real-world applications, such as dichotomy-based constraint encoding and scheduling problems. Solving PCP for large graphs is still a challenge since it is NP-complete. In this article, we first propose a key concept called a partition independent set (PIS) and design an efficient algorithm called FastPIS to find a maximum PIS. By applying FastPIS with a simple coloring procedure, we can obtain a high-quality initial solution for PCP. Moreover, we propose a reduction rule based on another novel concept called an l-clustering-degree bound ordered set (l-CDBOS), by which the scale of the working graph can be iteratively reduced. Based on these techniques, we develop an efficient method called HotPGC for solving PCP. The proposed algorithm is evaluated on benchmark graphs, and computational results show that HotPGC achieves highly competitive performance, compared with the state-of-the-art algorithms. The influence of the proposed reduction rule on the efficiency of HotPGC is also analyzed.

Automated summary

This article investigates effective solving methods for the partition coloring problem (PCP). Firstly, a concept called partition independent set (PIS) is proposed and an algorithm called FastPIS is designed to find the maximum PIS. By combining with a coloring process, a high-quality initial solution for PCP can be obtained. Secondly, a reduction rule based on another concept called l-clustering-degree bound ordered set (l-CDBOS) is introduced to iteratively reduce the scale of the working graph. Based on these techniques, an efficient method called HotPGC is developed to solve PCP. Experimental results show that HotPGC achieves highly competitive performance compared with state-of-the-art algorithms.