2000/06/30 by Richard Beigel, David Eppstein · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bayesian Modeling and Causal Inference #Combinatorics #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Discrete mathematics #Graph #Mathematics #Satisfiability #Time complexity #Variable (mathematics) #Vertex (graph theory) #cs.DS
paper · pdf · doi:10.1016/j.jalgor.2004.06.008
published as J. Algorithms 54:2 (2005) 168-204 · 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
arxiv created 2000/06/30 · openalex publication_date 2004/08/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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.