A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition

Introduction

Given a simple undirected graph G = (V(G), E(G)), where V(G) = {v₁, v₂, …, v_n} is a set of n vertices (n is usually called the “order” of G) and E(G) ⊂ V(G) × V(G) a set of m edges, and a set C = {c₁, c₂, …, c_k} of k colors, a k-coloring of G is any assignment of one of the k available colors from C to every vertex in V(G). More formally, a k-coloring of G is a mapping c: V(G) → C. The k-coloring problem (k-COL) is to find such a mapping (or prove that none exists) such that adjacent vertices receive different colors (called “proper” k-coloring). More formally, a proper k-coloring of G verifies {v_i, v_j} ∈ E(G) → c(v_i) ≠ c(v_j). The tightly related optimization version of k-COL is the graph coloring problem (COL): Determine a proper k-coloring of G with k minimum, i.e. the chromatic number χ(G).

k-COL is known to be NP-complete when k ≥ 3 for general graphs (Garey & Johnson, 1979; Karp, 1972). It remains NP-complete even for particular classes of graphs, including, for instance, triangle-free graphs with maximum degree 4 (Maffray & Preissmann, 1996). Classes of graphs for which 3-COL can be decided in polynomial time are discussed, for instance, in (Alekseev et al., 2007; Kochol et al., 2003).

Another way to express the difficulty of a combinatorial search problem is to consider the phase transition phenomenon which refers to the “easy-hard-easy” transition regions where a problem goes from easy to hard, and conversely (Cheeseman et al., 1991; Dubois et al., 2001; Gent et al., 1996; Hartmann & Weigt, 2005; Hogg et al., 1996; Monasson et al., 1999), see also (Barbosa & Ferreira, 2004; Krzakała et al., 2004; Zdeborová & Krzakała, 2007) for k-COL. Various phase transition thresholds (noted τ hereafter) have been identified for some classes of random graphs. For 3-COL, τ seems to occur when the edge probability p is such that 2pn/3 ≈ 16/3 according to Petford & Welsh (1989) (referred as τ_w in the rest of the paper), when the mean connection degree 2m/n ≈ 5.4 (τ_c from Cheeseman et al. (1991)), when 7/n ≤ p ≤ 8/n (τ_h from Eiben, van der Hauw, & van Hemert, 1998), when 2m/n ≈ 4.6 (τ_g from Culberson & Gent, 2001), or when p ≈ 3/n + 3(n - 3)(1 – 1/6^2/n)/2n (τ_e from Erben (2001)). Note that τ_e and τ_w are similar to the upper bound of τ_h (8/n). τ_c and τ_g are also similar but τ_c holds only for graphs that are first transformed (before solving) using three “particular reduction operators” (Cheeseman et al., 1991). Additionally, τ_e was characterized just for equipartite graphs and τ_w only for equipartite and uniform graphs. Henceforth, we use the terminology outside of τ_h (or τ_c or τ_g, etc.) to indicate parameter values outside of the indicated τ setting.