A Reduction based Method for Coloring Very Large Graphs

1 Introduction

The graph coloring problem (GCP), also known as vertex coloring problem, requires to find an assignment of colors to vertices of a graph such that no two adjacent vertices share the same color while minimizing the number of colors. GCP is a fundamental combinatorial optimization problem and is NP-hard [Garey and Johnson, 1979], even to approximate within n1-ϵ [Zuckerman, 2007]. It has been extensively studied not only for its theoretical aspects and for its difficulty, but also for its applications in many fields, including scheduling [Leighton, 1979], timetabling [de Werra, 1985], register allocation [Chow and Hennessy, 1990], and more recently to human subjects [Kearns et al., 2006], among many others.

Recent advances in information technology, as well as the rapid growth of the Internet, have resulted in very large scale data sets. Many data sets can be modeled as graphs, and the study of massive real world graphs, also called complex networks, grew enormously in last decade. Many real world graphs of interest are very large (e.g., with tens of millions of vertices), and sparse, and the vertex degrees usually follow a power-law distribution [Newman, 2003]. Nevertheless, GCP remains hard to approximate when restricted to power-law graphs, unless NP = ZPP [Shen et al., 2012].

∗Corresponding author

Despite its practical importance, there is limited research on solving GCP in massive graphs. Most literature devoted to solving it focuses on small graphs with up to thousands of vertices [Br´elaz, 1979] [Campˆelo et al., 2008] [Hansen et al., 2009] [Malaguti et al., 2011] [Gualandi and Malucelli, 2012] [Hao and Wu, 2012].

Many existing algorithms for GCP become futile on massive graphs, due to their high space complexity and time complexity. For example, most GCP algorithms heavily rely on an adjacency matrix representation of the graph. Graphs with millions of vertices can not fit into a computer's working memory using this representation. Also, most commonly used strategies do not have sufficiently low time complexity, which severely limits their ability to handle massive graphs.

There has not been research on solving GCP in massive graphs until recent years. Rossi et al. proposed a method for coloring complex networks, which leverages triangles, triangle-cores and other properties and their combinations [Rossi and Ahmed, 2014]. Verma et al. exploited the k-core concept [Seidman, 1983] and developed an algorithm for GCP by successively coloring k-cores with decreasing k values [Verma et al., 2015]. Peng et al. proposed a vertex-cut based method which partitions a graph into connected components and color them respectively. [Peng et al., 2016].

In this work, we propose a novel method for solving GCP on massive sparse graphs. The method is based on a key concept called degree bounded independent set. An important observation is that we can reduce the graph by removing an ℓ-degree bounded independent set (ℓ is the lower bound of the chromatic number) while preserving optimal solutions. That is, any optimal solution to the remained graph can be extended to an optimal solution to the original graph by coloring the removed vertices iteratively. To improve the efficiency, we propose a heuristic algorithm for finding a high-quality clique, which serves as a lower bound; also, for improving the upper bound, we propose a heuristic algorithm to color the whole graph after each round of reduction. We implement our method and it is named FastColor.

We carry out extensive experiments to evaluate the performance of FastColor on massive graphs, including real world graphs from various application fields. Experimental results show that, the solutions obtained by our method in quite short time limit (i.e., one minute) are nearly optimal and provably optimal for most instances. Particularly, for 97 out of 144 tested graphs, FastColor finds and proves an optimal solution in one minute. When compared with state of the art algorithms for GCP in massive graphs, FastColor also shows its superiority by finding better solutions, using much less time.

In the next section, we introduce some background knowledge. Then, we introduce a reduction rule for GCP based on degree bounded independent set in Section 3. After that, we describe the top-level algorithm of our method in Section 4, and its important components in Section 5. Experimental evaluations are presented in Section 6.

2 Preliminaries

Let G=(V ,E) be an undirected graph where V ={v1, v2, . . ., vn} is the set of vertices and E is the set of edges. Each edge is a 2-element subset of V . For a vertex v, its neighborhood is N(v)={u ∈ V |{u, v} ∈ E}, and its degree is d(v) = |N(v)|. An edge e is called an incident edge of a vertex v iff v ∈ e. For a subset V ′ ⊆ V , we let G[V ′ ] denote the subgraph induced by V ′ , which is formed from V ′ and all of the edges connecting pairs of vertices in V ′ . Also, for a vertex v ∈ V ′ , we define dG[V ′ ](v) = |N(v) ∩ V ′ |.

For a graph, a proper coloring is an assignment α of colors to all vertices of the graph such that no two adjacent vertices share the same color, and we say such a coloring colors the graph properly. We use color(α) to denote the set of colors used in a coloring α, and thus the number of colors used is |color(α)|. The chromatic number of G, denoted as χ(G), is the smallest number of colors needed to color G properly. For a vertex v under α, the color assigned to it is colorV alue(v).

Given a graph G, a clique C is a set of pairwise adjacent vertices, while an independent set I is a set of pairwise nonadjacent vertices. A clique or independent set is maximal if it is not included in a larger clique or independent set. The clique number of a graph G, denoted as ω(G), is the number of vertices in the largest clique. We have χ(G) ≥ ω(G).

3 AReduction Rule for Coloring

In this section, we introduce a reduction technique for GCP. Generally speaking, for a graph G, the idea is to decompose the graph into two parts, with the help of a lower bound on the chromatic number χ(G). For convenience, let us call one of them kernel while the other margin. We then reduce the graph by removing the margin, and seek for a proper coloring for the kernel. 1 Our reduction rule grantees that, any optimal solution for the kernel can be extended into an optimal solution for the original graph by coloring the removed margin iteratively. The power of our method also relies on the fact that, the reduction can be executed iteratively (i.e., a kernel can be taken as a new graph and be reduced again), while preserving the optimal solutions.

1 The removed vertices and incident edges are stored in some data structure, so that they can be colored after the kernel is colored.

3.1 Reduction based on BIS

The proposed reduction rule for GCP is based on a concept called degree bounded independent set, which is formally defined as follows.

Definition 1 Given a graph G = (V, E), a k-degree bounded independent set is an independent set I s.t. ∀v ∈ I, d(v) < k.

With the above definition, we propose a reduction rule denoted as BIS-Rule, where BIS stands for Bounded Independent Set. Additionally, we prove an important property about the rule.

BIS-Rule: Given a graph G = (V, E) and a lower bound on χ(G), denoted as ℓ, find an ℓ-degree bounded independent set I, and remove all vertices in I and their incident edges from G.

Note that the rule depends on a parameter ℓ, which is a lower bound on χ(G).

Proposition 1 Given a graph G = (V,E) and an ℓ-degree bounded independent set I in it, and χ(G) ≥ ℓ,

Proof: Let us denote G′ = G[V \ I]. Since I is an independent set, ∀v ∈ I, N(v) ⊆ V (G′ ).

1) The case χ(G′ ) < ℓ. For any vertex v ∈ I, suppose under an optimal coloring to G′ , vertices in N(v) are assigned with colors c1, c2,..., cd(v), where each ci ∈ {1, 2, ..., χ(G′ )} and the values of ci are not necessarily different to each other. Let CN(v) denote the set of colors assigned to N(v). As χ(G′ ) + 1 /∈ CN(v), we can assign color χ(G′ ) + 1 to vertex v without causing any conflict. Similarly, all other vertices in the independent set I can be assigned with color χ(G′ )+1. In this way, we obtain a proper coloring for graph G, using χ(G′ ) + 1 colors. Thus, we have

On the other hand, χ(G) ≥ ℓ. Put them together, we have χ(G) = ℓ, and the coloring for G constructed in this way is optimal.

2) The case χ(G′ ) ≥ ℓ. For any vertex v ∈ I, suppose under an optimal coloring to G′ , CN(v) is the set of colors assigned to N(v). (a) CN(v) ⊆ {1, 2, ..., χ(G′ )} and |CN(v)| ≤ d(v). (b) As I is ℓ-bounded, ∀v ∈ I, d(v) < ℓ. (c) The assumption states χ(G′ ) ≥ ℓ. Put (a), (b), (c) together, we have

So, there exists a color c′ ∈ {1, 2, ..., χ(G′ )} s.t. c′ /∈ CN(v). We can assign this color c′ to vertex v without causing any conflict. Similarly, all other vertices in I can be assigned with a color in {1, 2, ..., χ(G′ )} safely. In this way, we obtain a proper coloring for G, using χ(G′ ) colors. Thus, we have χ(G) ≤ χ(G′ ). On the other hand, since G′ is a subgraph of G, χ(G) ≥ χ(G′ ). Therefore, χ(G) = χ(G′ ), and the coloring for G constructed in this way is optimal. □

Proposition 1 shows that the BIS-Rule is sound, that is, we can always construct an optimal coloring for the original graph G from an optimal coloring for a graph G′ which is reduced from G by the BIS-Rule. In our proof, we also show the construction method, which is very simple. When the found coloring for G′ is not proved to be optimal, this construction method obtains a heuristic coloring for G.

We would like to note that, our reduction technique is essentially different from the previous 'Independent Set Extraction' method [Wu and Hao, 2012], which preprocesses the graph by iteratively removing an independent set and assigning a color to it. The 'Independent Set Extraction' method does not grantee to reserve the optimal solution after extracting an independent set. Indeed, for large graphs, many largest (extracted) independent sets are not part of an optimal coloring [Galinier et al., 2013]. In this case, removing these independent sets will prevent inevitably the subsequent coloring algorithm from reaching an optimal coloring.

3.2 On Lower Bound Used in Reduction

As we have shown, the BIS-Rule exploits a lower bound on the chromatic number . Thus, before each round of reduction, we need to calculate a lower bound for the remained graph.

It is important to note that, any lower bound for any subgraph of G is a lower bound on χ(G) for the original input graph G. This is formally expressed in the following lemma.

Lemma 1 Given a graph G = (V,E), for any subgraph G′ = (V ′ ,E′ ) of G, that is, V ′ ⊆ V or E′ ⊆ E (or both), then χ(G) ≥ χ(G′ ).

The proof is trivial by contradiction. If there is a proper coloring, say α, with less than χ(G′ ) colors for G, the projection on V ′ of α is also a proper coloring of G′ . □

In our method, we find a lower bound of the chromatic number via finding a clique, as the clique number is a lower bound of the chromatic number. Although simple, cliquebased lower bound is particularly effective in our reductionbased method. To see this, suppose the best found clique before some round of reduction is of size k, then the vertices removed by BIS-Rule are all of degree less than k. Therefore, any clique with size larger than k is reserved in the graph, while at the same time, the graph is reduced to a smaller size, which makes finding a larger clique more easily. Hence, as the algorithm processes, we can expect to find larger cliques, so that the lower bound on χ(G) is likely refined.

4 The Main Algorithm: FastColor

In this section, we introduce the top-level algorithm of our method named FastColor. Before going to detailed descriptions of the algorithm, we first introduce some notation.

G is the original graph, while Gk is the working graph which is reduced from G and becomes smaller during the algorithm. Gm collects all the vertices that have been removed from G, and removed edges are also stored accordingly (although not reflected in pseudo code). Notation lbk denotes the lower bound on χ(Gk), while lb∗ and ub∗ denote the best found lower bound and upper bound on χ(G) respectively, and α∗ denotes the best coloring found so far.

Algorithm 1: FastColor (G)

Input: a graph G = (V, E) Output: A coloring assignment of G 1 Gk := G; 2 lb∗ := 0, ub∗ := |V |, α∗ = ∅; 3 lbk := 0, isColored = false; 4 while elapsed time < cutoff do 5 lbk := FindClq(Gk, lbk); 6 if lbk > lb∗ then lb∗ := lbk; 7 I := find a maximal lbk-degree bounded independent set; 8 Gk := remove I fromGk according to BIS-Rule; 9 Gm := Gm ∪ I; 10 if I ̸= ∅ then 11 lbk := 0, isColored := false 12 α := ColorKernel(Gk, isColored); 13 α+ := a proper coloring for G extended fromα by coloring vertices in Gm; 14 isColored := true; 15 if |color(α+)| < ub∗ then 16 α∗ := α+, ub∗ := |color(α+)| 17 if ub∗ := lb∗ then return α∗ ; 18 return α∗ ;

In the beginning, the working graph Gk is initialized as G; lb∗ , ub∗ and α∗ are also initialized. After the initialization, a loop (lines 4-17) is executed until an optimal solution is proved (line 17) or a given time limit is reached. FastColor returns the best found coloring α∗ for G upon reaching the termination condition (line 18).

Each iteration of the loop can be seen as three phases:

Lower bound computation (lines 5-6): The lower bound lbk is computed by finding a clique in Gk. Since lbk can also serve as a lower bound on χ(G), if lbk is smaller (thus tighter) than lb∗ , lb∗ is updated accordingly.

Graph reduction (lines 7-9): To reduce the graph, we first find a maximal lbk-degree bounded independent set. This is accomplished by traversing Gk sequentially and adding the vertex if its degree is less than lbk and it is not adjacent to any vertex already in the independent set. Then, Gk is reduced by removing I, according to the BIS-Rule. Along with this reduction, removed vertices (and the removed incident edges) are stored into Gm. Note that sometimes the BIS-Rule cannot remove any vertex, and in this case, Gk is unchanged.

Graph coloring (lines 12-16): after the reduction, the original graph G is colored in two steps. First, the working graph Gk is colored by a coloring algorithm named ColorKernel. Then, the obtained coloring α for Gk is extended to a coloring α+ for G by coloring Gm. This is accomplished iteratively, i.e., in each iteration the most recently removed uncolored independent set is colored, using a construction method as shown in the proof of Proposition 1. Finally, if the number of colors in α+ is less than ub∗ , then ub∗ is updated accordingly.

Additionally, if ub∗ meets lb∗ , then a proved optimal coloring is found and returned (line 17).

5 Important Functions

In this section, we introduce two important functions (indeed sub-algorithms) in FastColor, one for finding clique before each round of reduction, while the other for coloring the remained graph after each round of reduction.

5.1 The FindClq Algorithm

We employ a construct-and-cut heuristic method [Cai and Lin, 2016] to find a high-quality clique from the remained graph. This algorithm, named FindClq (Algorithm 2), can be viewed as a series of clique samples from the graph.

We use C to denote the current clique under construction, and StartSet is the set containing vertices candidate as a starting vertex to construct a clique. CandSet = {v|v ∈ N(u) for ∀u ∈ C} consists of candidate vertices eligible to extend the current clique.

Algorithm 2: FindClq (G, lb)

Input: A graph G = (V, E), lower bound of clique size lb Output: The size of best found clique 1 lbold := lb; 2 StartSet := a set of random vertices from V ; 3 while StartSet ̸= ∅ do 4 u := pop a random vertex from StartSet; 5 C := {u}; 6 CandSet := N(u); 7 while CandSet ̸= ∅ do 8 v := a vertex with greatest |N(v) ∩ CandSet| value among t samples fromCandSet; 9 if |C| + 1 + |N(v) ∩ CandSet| ≤ lb then Break; 10 C := C ∪ {v}; 11 CandSet := CandSet \ {v}; 12 CandSet := CandSet ∩N(v); 13 if |C| > lb then lb := |C| ; 14 if lbold = lb then adjust BMS parameter t; 15 return lb;

The FindClq algorithm employs the BMS heuristic [Cai, 2015] in choosing the vertex to be added to the current clique. BMS heuristic returns the best element w.r.t. some comparison function among t samples (with replacement) from a given set. Since different t values correspond to different levels of greediness, we try several t values in [1, tmax], where tmax is a parameter that needs to be specified, and is set to 64 in our experiments. We use a formula t := 2t to get the next t value when FindClq fails to find a larger clique after trying each vertex from StartSet as the starting vertex (line 14). Also, when t exceeds tmax, it is reset to 1.

First, the algorithm chooses some random vertices from V to initialize the StartSet (line 2). In our algorithm, the size of StartSet is set to |V | 100 . Then, the algorithm executes a loop until StartSet becomes empty (lines 3-13), each iteration of which constructs a clique from a random vertex u popped from StartSet (line 5). Along with adding the starting vertex u, CandSet is initialized as N(u) (line 6). Then, the clique is extended by iteratively adding a vertex v with the greatest value of |N(v)∩CandSet| among t samples fromCandSet, until CandSet becomes empty (lines 7-12).

Also, we use a cost-effective upper bound to prune the procedure (lines 9). Obviously, |C| + 1 + |N(v) ∩ CandSet| is an upper bound on size of any clique extended from C by adding v and more vertices.

At the end of a clique construction procedure, the lower bound of clique size lb is updated accordingly (line 13). Finally, when F indClq terminates, it returns lb (line 14), which is used as a lower bound on the chromatic number.

5.2 The ColorKernel Algorithm

To color the kernel, we employ the concepts of k-core [Seidman, 1983] and saturation degree [Br´elaz, 1979]

Definition 2 Given a graph G = (V,E) and a subset of vertices V ′ ⊆ V , a subgraph G[V ′ ] is called a k-core if dG[V ′ ](v) ≥ k for ∀v ∈ V ′ .

Definition 3 Given a graph G = (V, E) and a partial coloring assignment α, the saturation degree of a vertex is defined as the number of different colors used by N(v) under α.

If the graph G has not been colored (after each successful reduction, see Algorithm 1), we sort V according to core decomposition of G [Batagelj and Zaversnik, 2003] (line 3). This partitions V into smaller parts based on k-cores, and vertex in k-core with larger k has a larger index in V . Then we color V in decreasing array-index order (lines 4-7). Each vertex is colored with a minimum possible color.

Otherwise, we color V in an order depending on saturation degree. In each iteration, a vertex v with maximum saturation degree (breaking tie randomly) is selected (line 10) and is colored with a minimum possible color (line 12). To accelerate the selection operation, we use a bucket for each saturation degree to store the vertices of that saturation degree.

Algorithm 3: ColorKernel (G, isColored)

Input: a graph G = (V, E), isColored Output: a coloring assignment of G 1 α := ∅; 2 if isColored = false then 3 sort V according to core decomposition of G; 4 for each v ∈ V in decreasing array-index order do 5 c := min{i > 0 | ∀u ∈ N(v), colorV alue(u) ̸= i} ; 6 if c > |color(α)| then c :=recolor(v) ; 7 α := α ∪ (v, c); 8 else 9 while V ̸= ∅ do 10 v :=a vertex from V with maximum saturation degree; 11 V := V \ v; 12 c := min{i > 0 | ∀u ∈ N(v), colorV alue(u) ̸= i} ; 13 if c > |color(α)| then c :=recolor(v) ; 14 α := α ∪ (v, c); 15 update saturation degree accordingly;

16 return α;

During the coloring of a vertex v, if the minimum possible color is a new color, we use the recolor procedure [Rossi and Ahmed, 2014] to avoid increasing the color number (lines 6, 13). It tries to change the color of v's neighbors, so that v can be colored with an existing color. Tomita et al. also use this technique in their MCS algorithm [Tomita et al., 2010].

6 Experimental Evaluation

We conduct experiments on a broad range of real-world massive graphs to compare FastColor with two state of the art GCP algorithms proposed in [Rossi and Ahmed, 2014] and [Verma et al., 2015]. These algorithms do not have names in the literatures, and are referred to as Rossi's algorithm and Verma's algorithm for convenience. We also like to compare FastColor with previous 'Independent Set Extraction' method [Wu and Hao, 2012], but the results on massive graphs are not available to us.

6.1 Experimental Preliminaries

FastColor is implemented in C++ and compiled with g++ version 4.8.4 with -O3 option. The experiments are carried out on a workstation under Ubuntu 14.04, using 2 cores of Intel i7-4710MQ CPU @ 2.50 GHz and 16 GB RAM.

We run FastColor 10 times on each graph, with a cutoff time of 60 seconds per run. For each graph, we report the minimum number of colors ("Min") found by FastColor, and the average number of colors over all runs ("Avg") if a 100 percent success rate is not reached. Besides, we also report the average runtime ("Time") of FastColor over all runs, where the runtime of an execution is the time it needs to find and prove the optimal solution if it proves the optimality, and the time to find the best coloring assignment otherwise. The number of reduction iterations ("#Iter.") is also shown.

Since the source code or binary of Rossi's and Verma's algorithm are not available to us, we compared FastColor with them using the results ("Min" and "Time") reported in the corresponding papers. The experimental environment of Rossi's algorithm is not reported in [Rossi and Ahmed, 2014], while Verma's algorithm was run on a workstation under windows 7, with two Intel E5620 CPU @ 2.40 GHz and 12 GB RAM. Despite the difference of platforms, we can still draw a conclusion clearly from the comparison that FastColor outperforms Rossi's and Verma's algorithms.

6.2 Results on Network Data Repository

In this subsection, we compare FastColor with Rossi's algorithm on the benchmarks from Network Data Repository online [Rossi and Ahmed, 2015]. 2 Rossi's algorithm has several variants [Rossi and Ahmed, 2014], and we compare FastColor with the best one, i.e., TCORE-VOL with recolor procedure. As the runtime of TCORE-VOL with recolor is missing, we instead report the runtime of TCORE-VOL without recolor procedure (which seems to be shorter than it should be). The results of this variant on some instances are not reported in the literature, and we take the best solution we can find in [Rossi and Ahmed, 2014] and mark the runtime as '-'.

The results are presented in Tables 1 and 2. For all the 91 instances, FastColor obtains better or same-quality solutions when compared with Rossi's algorithm. In detail, FastColor obtains better solutions on 59 instances. For the remaining 32 instances, the two algorithms obtain the same solutions. Further observations show that both algorithms prove the optimal solution for these 32 instances except one, which indicates that these 32 instances might be relatively easy. In addition, FastColor proves the optimality for 64 instances, while Rossi's algorithm does so for only 31 instances.

2 http://www.graphrepository.com/networks.php

6.3 Results on SNAP and DIMCAS10

The benchmarks used in [Verma et al., 2015] were originally from Stanford Large Network Dataset Collection, 3 and the 10th DIMACS implementation challenge. 4 In this subsection, we compare FastColor with Verma's algorithm on these benchmarks, which contains totally 53 instances.

The results are presented in Table 3. We focus on comparing the solution quality. For the 53 instances, FastColor performs better than Verma's algorithm on 19 instances, while worse on only 2 instances. For the remaining

3 http://snap.stanford.edu/data

4 http://www.cc.gatech.edu/dimacs10/

32 instances, FastColor and Verma's algorithm obtain the same solution quality, and prove the optimal solution for all except one instance (333SP), indicating these 32 instances might be relatively easy.

It is not so scientific to compare the runtime under different platform. Nevertheless, the significant gap still demonstrates the superiority of FastColor in terms of run time. FastColor is much faster than Verma's algorithm. With regard to averaged time, FastColor is 10 times faster for 27 instances and 100 times faster for 18 instances. In particular, Verma's algorithm needs more than 10 thousand seconds to obtain a 5 colors assignment for 333P, while FastColor only need 2 seconds.

7 Summary and FutureWork

This paper presented a novel graph coloring algorithm for coloring massive graphs within short time. We proposed a reduction rule which is based on a novel concept called degree bounded independent set. The method iteratively executes this rule by interleaving between lower bound computation and graph reduction. Experiments on real-world large graphs show that FastColor is very fast and finds better solutions than state of the art algorithms.

We would like to explore more reduction rules for GCP, such as heuristic rules. Another direction is to apply similar method to other graph problems.

Acknowledgements

This work is partially supported by the National Natural Science Foundation of China under Grant 61502464, Grant 61472369, and Grant 61370072, partially supported by the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing under Grant 2016A06, and partially supported by the Australian Research Council under Grant DP150101618. Shaowei Cai is also supported by Youth Innovation Promotion Association, Chinese Academy of Sciences.