VColor*: a practical approach for coloring large graphs

Abstract

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-andconquer 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-ofthe- art graph coloring methods.

Keywords

graph coloring / approximation algorithm / distributed algorithm

References

[1] Peng Y, Choi B, He B, Zhou S, Xu R, Yu X. Vcolor: a practical vertexcut based approach for coloring large graphs. In: Proceedings of IEEE International Conference on Data Engineering. 2016, 97–108

[2] Ingrid A. Nucleic acid sequence design as a graph colouring problem. Thesis, Universitat Wien, 2005, 1–83

[3] Park T, Lee C Y. Application of the graph coloring algorithm to the frequency assignment problem. Journal of the Operations Research of Japan, 1996, 39(2): 258–265

[4] Chaitin G. Register allocation and spilling via graph coloring. ACM Sigplan Notices, 1982, 17(6): 98–101

[5] Lotfi V, Sarin S. A graph coloring algorithm for large scale scheduling problems. Computers & Operations Research, 1986, 13(1): 27–32

[6] Moradi F, Olovsson T, Tsigas P. A local seed selection algorithm for overlapping community detection. In: Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2014, 1–8

[7] Yuan L, Qin L, Lin X, Chang L, Zhang W. Diversified top-k clique search. In: Proceedings of IEEE International Conference on Data Engineering. 2015, 387–398

[8] Hertz A, De Werra D. Using tabu search techniques for graph coloring. Computing, 1987, 39(4): 345–351

[9] Halldøsrsson M M. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993, 45(1): 19–23

[10] Galinier P, Hao J K. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 1999, 3(4): 379–397

[11] Galinier P, Hamiez J P, Hao J K, Porumbel D. Recent advances in graph vertex coloring. Handbook of Optimization, 2013, 38: 505–528

[12] Karger D, Motwani R, Sudan M. Approximate graph coloring by semidefinite programming. Journal of the ACM, 1998, 45(2): 246–265

[13] Pardalos P M, Mavridou T, Xue J. The Graph Coloring Problem: a Bibliographic Survey. Handbook of Combinatorial Optimization, Springer, Boston, 1999, 1077–1141

[14] Husfeldt T. Graph Colouring Algorithms. Cambridge University Press, 2015, 277–303

[15] Kuhn F, Wattenhofer R. On the complexity of distributed graph coloring. In: Proceedings of ACM Symposium on Principles of Distributed Computing. 2006, 7–15

[16] Eppstein D. All maximal independent sets and dynamic dominance for sparse graphs. ACM Transactions on Algorithms, 2009, 5(4): 1–14

[17] Byskov J M. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 2004, 32(6): 547–556

[18] Feige U, Mahdian M. Finding small balanced separators. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2006, 375–384

[19] Johnson D J, Trick M A. Cliques, Coloring, and Satisfiability. Boston, MA, USA: American Mathematical Society, 1996

[20] Lee J, Han W S, Kasperovics R, Lee J H. An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proceedings of the VLDB Endowment, 2012, 6(2): 133–144

[21] Jones M T, Plassmann P E. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 1993, 14(3): 654–669

[22] Salihoglu S, Widom J. Optimizing graph algorithms on pregel-like systems. Proceedings of the VLDB Endowment, 2014, 7(7): 577–588

[23] Yuan L, Qin L, Lin X, Chang L, Zhang W. Effective and efficient dynamic graph coloring. Proceedings of the VLDB Endowment, 2017, 11(2): 338–351

[24] Barba L, Cardinal J, Korman M, Langerman S, Renssen V A, Roeloffzen M, Verdonschot S. Dynamic graph coloring. Algorithmica, 2019, 81(4): 1319–1341

[25] Blöchliger I, Zufferey N. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008, 35(3): 960–975

[26] Porumbel D, Hao J K, Kuntz P. A study of evaluation functions for the graph k-coloring problem. Artificial Evolution, 2008, 4926: 124–135

[27] Hertz A, Plumettaz M, Zufferey N. Variable space search for graph coloring. Discrete Applied Mathematics, 2008, 156(13): 2551–2560

[28] Morgenstern C, Shapiro H. Coloration neighborhood structures for general graph coloring. In: Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms. 1990, 226–235

[29] Fleurent C, Ferland J. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 1996, 63(3): 437–461

[30] Galinier P, Hertz A, Zufferey N. An adaptive memory algorithm for the k-coloring problem. Discrete Applied Mathematics, 2008, 156(2): 267–279

[31] Porumbel D C, Hao J K, Kuntz P. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, 2010, 37(10): 1822–1832

[32] Lü Z, Hao J K. A memetic algorithm for graph coloring. European Journal of Operational Research, 2010, 203(1): 241–250

[33] Chams M, Hertz A, De Werra D. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 1987, 32(2): 260–266

[34] Johnson D S, Aragon C R, McGeoch L A, Schevon C. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 1991, 39(3): 378–406

[35] Wu Q, Hao J K. Coloring large graphs based on independent set extraction. Computers & Operations Research, 2012, 39(2): 283–290

[36] Wu Q, Hao J K. An extraction and expansion approach for graph coloring. Asia-Pacific Journal of Operational Research, 2013, 30(5): 1350018

[37] Hao J K, Wu Q. Improving the extraction and expansion method for large graph coloring. Discrete Applied Mathematics, 2012, 160(16–17): 2397–2407

[38] Schneider J, Wattenhofer R. A new technique for distributed symmetry breaking. In: Proceedings of ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. 2010, 257–266

[39] Luby M. A simple parallel algorithm for the maximal independent set problem. In: Proceedings of Annual ACM Symposium on Theory of Computing. 1985, 1–10

[40] Cole R, Vishkin U. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 1986, 70(1): 32–53

[41] Linial N. Locality in distributed graph algorithms. SIAMJournal on Computing, 1992, 21(1): 193–201

[42] Szegedy M, Vishwanathan S. Locality based graph coloring. In: Proceedings of ACM Symposium on Theory of Computing. 1993, 201–207

[43] Panconesi A, Srinivasan A. On the Complexity of Distributed Network Decomposition. Academic Press, Inc., 1996

[44] Barenboim L, Elkin M, Kuhn F. Distributed (delta+ 1)-coloring in linear (in delta) time. Siam Journal on Computing, 2014, 43(1): 72–95

[45] Checco A, Leith D J. Fast, responsive decentralized graph coloring. IEEE/ACM Transactions on Networking, 2017, 25(6): 3628–3640

RIGHTS & PERMISSIONS

Higher Education Press