VColor: A practical vertex-cut based approach for coloring large graphs

Yun PENG, Koon Kau CHOI, Bingsheng He, Shuigeng Zhou, Ruzhi Xu, Xiaohui Yu

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

9 Citations (Scopus)

Abstract

Graph coloring is a fundamental NP-hard problem in graph theory. It has a wide range of real applications, such as Operations Research, Communication Network, Computational Biology and Compiler Optimization. Notable efforts have been spent on designing its approximation algorithms. Halldrsson proposed the algorithm (denoted as SampleIS) with the current best known approximation ratio. However, its time complexity is O(|G|3), where |G| is the number of vertices of a graph G. It is clear that SampleIS is not practical for large graphs. In this paper, we propose a practical vertex-cut based coloring technique (VColor) for coloring large graphs. First, we partition G into k connected components (CCs) of a small size s by removing a vertex-cut component (VCC). For each CC, we apply our novel coloring algorithm, based on maximal independent set enumeration. The approximation ratio and the time complexity for coloring the k CCs are log s + 1 and O(ks23s/3), respectively, whereas those of SampleIS are ks(log log ks)2/ log3 ks and O(k3s3). For the VCC, we simply apply SampleIS. To combine the colorings of the CCs and the VCC, we propose a maximum matching based algorithm. Second, in the context of a database of graphs, users may color many graphs. We propose an optimization technique, inspired by multi-query optimization, for coloring a set of graphs. We design a VP hierarchy (VPH) to represent the common subgraphs as the common CCs. Third, we propose techniques for determining the optimal values of the parameters of VColor. Our extensive experimental evaluation on real-world graphs confirms the efficiency and/or effectiveness of our proposed techniques. In particular, VColor is more than 500 times faster than SampleIS, and the number of colors used are comparable on real graphs Yeast and LS.

Original languageEnglish
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages97-108
Number of pages12
ISBN (Electronic)9781509020195
DOIs
Publication statusPublished - 22 Jun 2016
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: 16 May 201620 May 2016

Publication series

Name2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

Conference

Conference32nd IEEE International Conference on Data Engineering, ICDE 2016
Country/TerritoryFinland
CityHelsinki
Period16/05/1620/05/16

Scopus Subject Areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'VColor: A practical vertex-cut based approach for coloring large graphs'. Together they form a unique fingerprint.

Cite this