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

DOI10.1007/S00453-014-9883-7MaRDI QIDQ494789zbMATH OpenOpenAlexFDO

Authors Keith 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

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

Recommendations

• Complexity and approximability of parameterized MAX-CSPs
• Complexity and Approximability of Parameterized MAX-CSPs
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• A faster polynomial-space algorithm for Max 2-CSP
• CSP duality and trees of bounded pathwidth
• On regularity of Max-CSPs and Min-CSPs
• The approximability of MAX CSP with fixed-value constraints
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Approximating dense MAX 2-CSPs
• The parameterized complexity of maximality and minimality problems

Cites work

• scientific article; zbMATH DE number 2084268 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A measure \& conquer approach for the analysis of exact algorithms
• A new approach to proving upper bounds for MAX-2-SAT
• A partial k-arboretum of graphs with bounded treewidth
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• An exact algorithm for MAX-CUT in sparse graphs
• Automata, Languages and Programming
• Exact Algorithms for Maximum Independent Set
• Exact exponential algorithms.
• Forbidden minors characterization of partial 3-trees
• Fragmentability of graphs
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Maximum acyclic and fragmented sets in regular graphs
• New Bounds for MAX-SAT by Clause Learning
• New Upper Bounds for Maximum Satisfiability
• New exact algorithms for the 2-constraint satisfaction problem
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• On two techniques of combining branching and treewidth
• Open problems around exact algorithms
• Pathwidth of cubic graphs and exact algorithms
• Planarization and acyclic colorings of subcubic claw-free graphs
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• Topics in structural graph theory
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(5)

• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A faster polynomial-space algorithm for Max 2-CSP
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs
• Pathwidth of cubic graphs and exact algorithms

Describes a project that uses

Uses Software

• MAX-2-SAT

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494789)