TY - JOUR
T1 - VColor*
T2 - a practical approach for coloring large graphs
AU - Peng, Yun
AU - Lin, Xin
AU - Choi, Koon Kau
AU - He, Bingsheng
N1 - Funding Information:
Thanks to the support of NSF of China (61773167, 61929103), NSF of Shandong Province (ZR2019LZH006), NSF of Shanghai (17ZR1444900, HKRGC GRF 12201119, 12232716 and 12201518), QLUT Young Scholar Program (2018DBSHZ005).
PY - 2021/8
Y1 - 2021/8
N2 - Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-and-conquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-of-the-art graph coloring methods.
AB - Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-and-conquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-of-the-art graph coloring methods.
KW - approximation algorithm
KW - distributed algorithm
KW - graph coloring
UR - http://www.scopus.com/inward/record.url?scp=85104508668&partnerID=8YFLogxK
U2 - 10.1007/s11704-020-9205-y
DO - 10.1007/s11704-020-9205-y
M3 - Journal article
AN - SCOPUS:85104508668
SN - 2095-2228
VL - 15
JO - Frontiers of Computer Science
JF - Frontiers of Computer Science
IS - 4
M1 - 154610
ER -