3-Coloring in Time O(1.3289^n)

Abstract

We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.

31 pages, 22 figures. An earlier version of this paper was presented at the 36th IEEE Symp. Foundations of Comp. Sci., 1995, and appears as ECCC TR 95-033

References in corpus (1)

• Quasiconvex Analysis of Backtracking Algorithms

Cited by in corpus (9)

• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Determining L(2,1)-Span in Polynomial Space
• Word-representability of split graphs
• Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP
• On the dynamic width of the 3-colorability problem
• 3-colorability of graphs with minimum degree at least 6
• Coloring outerplanar graphs and planar 3-trees with small monochromatic components
• Using Combinatorics to Prune Search Trees: Independent and Dominating Set
• Faster algorithm for Unique $(k,2)$-CSP