×

3-coloring in time \(O(1.3289^n)\). (English) Zbl 1101.68716

Summary: We consider worst-case time bounds for several NP-complete problems, based on a Constraint Satisfaction (CSP) formulation of these problems: \((a,b)\)-CSP instances consist of a set of variables, each with up to \(a\) possible values, and constraints disallowing certain \(b\)-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to \((2,3)\)-CSP while 3-coloring and various related problems are special cases of \((3,2)\)-CSP; there is also a natural duality transformation from \((a,b)\)-CSP to \((b,a)\)-CSP. We show that \(n\)-variable \((3,2)\)-CSP instances can be solved in time \(\mathcal O(1.3645^n)\), that satisfying assignments to \((d,2)\)-CSP instances can be found in randomized expected time \(\mathcal O((0.4518d)^n)\); that 3-coloring of \(n\)-vertex graphs can be solved in time \(\mathcal O(1.3289^n)\); that 3-list-coloring of \(n\)-vertex graphs can be solvedin time \(\mathcal O(1.3645^n)\); that 3-edge-coloring of \(n\)-vertex graphs can be solved in time \(\mathcal O(2^{n/2})\), and that 3-satisfiability of a formula with \(t\) 3-clauses can be solved in time \(\mathcal O(n^{\mathcal O(1)}+1.3645^t)\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI