Fan Yi, Zhang Zaijun, Yu Quan, Lai Yongxuan, Su Kaile, Wang Yiyuan, Pan Shiwei, Latecki Longin Jan
School of Mathematics and Statistic, Qiannan Normal University for Nationalities, Duyun 558000, China.
Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province, Duyun 558000, China.
Entropy (Basel). 2023 Sep 24;25(10):1376. doi: 10.3390/e25101376.
The Minimum Vertex Weighted Coloring (MinVWC) problem is an important generalization of the classic Minimum Vertex Coloring (MinVC) problem which is NP-hard. Given a simple undirected graph G=(V,E), the MinVC problem is to find a coloring s.t. any pair of adjacent vertices are assigned different colors and the number of colors used is minimized. The MinVWC problem associates each vertex with a positive weight and defines the weight of a color to be the weight of its heaviest vertices, then the goal is the find a coloring that minimizes the sum of weights over all colors. Among various approaches, reduction is an effective one. It tries to obtain a subgraph whose optimal solutions can conveniently be extended into optimal ones for the whole graph, without costly branching. In this paper, we propose a reduction algorithm based on maximal clique enumeration. More specifically our algorithm utilizes a certain proportion of maximal cliques and obtains lower bounds in order to perform reductions. It alternates between clique sampling and graph reductions and consists of three successive procedures: promising clique reductions, better bound reductions and post reductions. Experimental results show that our algorithm returns considerably smaller subgraphs for numerous large benchmark graphs, compared to the most recent method named RedLS. Also, we evaluate individual impacts and some practical properties of our algorithm. Furthermore, we have a theorem which indicates that the reduction effects of our algorithm are equivalent to that of a counterpart which enumerates all maximal cliques in the whole graph if the run time is sufficiently long.
最小顶点加权着色（MinVWC）问题是经典的最小顶点着色（MinVC）问题的重要推广，而最小顶点着色问题是NP难问题。给定一个简单无向图G=(V,E)，最小顶点着色问题是找到一种着色方式，使得任意一对相邻顶点被赋予不同颜色，并且使用的颜色数量最少。最小顶点加权着色问题为每个顶点关联一个正权重，并将一种颜色的权重定义为其最重顶点的权重，那么目标是找到一种着色方式，使所有颜色的权重之和最小。在各种方法中，规约是一种有效的方法。它试图获得一个子图，其最优解可以方便地扩展为整个图的最优解，而无需进行代价高昂的分支操作。在本文中，我们提出了一种基于最大团枚举的规约算法。更具体地说，我们的算法利用一定比例的最大团并获得下界以进行规约。它在团采样和图规约之间交替进行，由三个连续的过程组成：有前景的团规约、更好的界规约和后规约。实验结果表明，与最新的名为RedLS的方法相比，对于众多大型基准图，我们的算法返回的子图要小得多。此外，我们评估了我们算法的个体影响和一些实际属性。此外，我们有一个定理表明，如果运行时间足够长，我们算法的规约效果与枚举整个图中所有最大团的对应算法的规约效果相同。
