Worst case analysis of a graph coloring algorithm

In this paper, we show that a graph coloring heuristic developed by Brélaz may use n colors to color a 3-colorable graph with O(n) vertices.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Trapezoid graphs and their coloring

We define trapezoid graphs, an extension of both interval and permutation graphs. We show that this new class properly contains the union of the two former classes, and that trapezoid graphs are equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. We provide an optimal coloring algorithm for trapezoid graphs that runs in time O(nk), where n is the number of nodes and k is the chromatic number of the graph. Our coloring algorithm has direct applications to channel routing on integrated circuits.     

Gibbs rapidly samples colorings of G(n, d/n)

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s–Rényi random graph G(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n, d/n) is d(1?o(1)), it contains many nodes of degree of order (log n) / (log log n). The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n, d/n) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n ^{1+Ω(1 / log log} n) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work we consider sampling q-colorings and show that for every d < ∞ there exists q(d) < ∞ such that for all q ≥ q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the “Weitz tree”, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erd?s–Rényi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which there exists an α > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Γ of length O(log n) satisfies ${\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}$ . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.     

Modelling gateway placement in wireless networks: Geometric k-centres of unit disc graphs

Motivated by the gateway placement problem in wireless networks, we consider the geometric k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P∪F. We show that the vertex 1-centre provides a 7-approximation of the geometric 1-centre and that a vertex k-centre provides a 13-approximation of the geometric k-centre, resulting in an O(kn)-time 26-approximation algorithm. We describe O(n²m)-time and O(n³)-time algorithms, respectively, for finding exact and approximate geometric 1-centres, and an O(mn2k)-time algorithm for finding a geometric k-centre for any fixed k. We show that the problem is NP-hard when k is an arbitrary input parameter. Finally, we describe an O(n)-time algorithm for finding a geometric k-centre in one dimension.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Perfect and locally perfect colorings

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m² + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random k ‐coloring of an n ‐vertex graph with maximum degree Δ. We prove that, for every ε > 0, the dynamics converges to a random coloring within O(nlog n) steps assuming k ≥ k₀(ε) and either: (i) k/Δ > α* + ε where α*≈? 1.763 and the girth g ≥ 5, or (ii) k/Δ >β * + ε where β*≈? 1.489 and the girth g ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on k/Δ and the minimum girth but also required Δ = Ω (log n). The best known result for general graphs is O(nlog n) mixing time when k/Δ > 2 and O(n²) mixing time when k/Δ > 11/6. Related results of Goldberg et al apply when k/Δ > α* for all Δ ≥ 3 on triangle‐free “neighborhood‐amenable” graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

We present an algorithm to compute, inO(m + n log n) time, a maximum clique in circular-arc graphs (withnvertices andmedges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity isO(m). The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem wasO(m log log n + n log n), using an algorithm that solved an independent subproblem for each of thencircular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log nfactor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain anO(m log log n + n log n) algorithm for finding a maximum-weight clique—which matches the best known algorithm.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

On list critical graphs

In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph K_nk-list critical. While this is the case for all 5≤k≤n, K_n is not 4-list critical if n is large.     

Uniquely colorable perfect graphs

This paper defines the concept of sequential coloring. If G or its complement is one of four major types of perfect graphs, G is shown to be uniquely k-colorable it and only if it is sequentially k-colorable. It is conjectured that this equivalence is true for all perfect graphs. A potential role for sequential coloring in verifying the Strong Perfect Graph Conjecture is discussed. This conjecture is shown to be true for strongly sequentially colorable graphs.     

Acyclic and star colorings of cographs

An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of star coloring requires that the union of any two color classes induces a disjoint collection of stars. We prove that every acyclic coloring of a cograph is also a star coloring and give a linear-time algorithm for finding an optimal acyclic and star coloring of a cograph. If the graph is given in the form of a cotree, the algorithm runs in O(n) time. We also show that the acyclic chromatic number, the star chromatic number, the treewidth plus 1, and the pathwidth plus 1 are all equal for cographs.