A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

DOI10.1007/s00453-014-9883-7zbMath1328.68089OpenAlexW2074729689MaRDI QIDQ494789

Keith J. Edwards, Eric J. McDermid

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://discovery.dundee.ac.uk/en/publications/c1d55881-e676-417d-b89a-43480fd4f770

zbMATH Keywords

treewidthpathwidthconstraint satisfaction problemsMax 2-CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• Exact exponential algorithms.
• Forbidden minors characterization of partial 3-trees
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Fragmentability of graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• An exact algorithm for MAX-CUT in sparse graphs
• Open problems around exact algorithms
• Exact Algorithms for Maximum Independent Set
• New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
• Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
• A measure & conquer approach for the analysis of exact algorithms
• New Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• New Upper Bounds for Maximum Satisfiability
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Maximum acyclic and fragmented sets in regular graphs
• Automata, Languages and Programming

This page was built for publication: A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP