标题：VColor: A Practical Vertex-cut Based Approach for Coloring Large Graphs
作者：Peng, Yun; Choi, Byron; He, Bingsheng; Zhou, Shuigeng; Xu, Ruzhi; Yu, Xiaohui
作者机构：[Peng, Yun; Xu, Ruzhi] Qilu Univ Technol, Res Ctr Big Data Applicat, Jinan, Shandong, Peoples R China.; [Choi, Byron] Hong Kong Baptist Univ, Dept C 更多
会议名称：32nd IEEE International Conference on Data Engineering (ICDE)
会议日期：MAY 16-20, 2016
来源：2016 32ND IEEE INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE)
摘要：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(vertical bar G vertical bar(3)), where vertical bar G vertical bar 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 (ks(2)3(s/3)), respectively, whereas those of SampleIS are ks (log log ks)(2) / log(3) ks and O(k(3)s(3)). 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.