On the equivalence among problems of bounded width

DOI10.1007/978-3-662-48350-3_63MaRDI QIDQ3452838zbMATH OpenOpenAlexFDO

Authors Yoichi Iwata, Yuichi Yoshida

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.01014

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: In this paper, we introduce a methodology, called decomposition-based reductions, for showing the equivalence among various problems of bounded-width. First, we show that the following are equivalent for any $alpha>0$: * SAT can be solved in $O^{\ast }(2^{alphamathrmtw})$ time, * 3-SAT can be solved in $O^{\ast }(2^{alphamathrmtw})$ time, * Max 2-SAT can be solved in $O^{\ast }(2^{alphamathrmtw})$ time, * Independent Set can be solved in $O^{\ast }(2^{alphamathrmtw})$ time, and * Independent Set can be solved in $O^{\ast }(2^{alphamathrmcw})$ time, where tw and cw are the tree-width and clique-width of the instance, respectively. Then, we introduce a new parameterized complexity class EPNL, which includes Set Cover and Directed Hamiltonicity, and show that SAT, 3-SAT, Max 2-SAT, and Independent Set parameterized by path-width are EPNL-complete. This implies that if one of these EPNL-complete problems can be solved in $O^{\ast }(c^k)$ time, then any problem in EPNL can be solved in $O^{\ast }(c^k)$ time.

Recommendations

• A note on width-parameterized SAT: an exact machine-model characterization
• Some remarks on the incompressibility of width-parameterized SAT instances
• Bounded-width QBF is PSPACE-complete
• scientific article; zbMATH DE number 6783432
• Known algorithms on graphs of bounded treewidth are probably optimal

Cites work

• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A note on exact algorithms for vertex ordering problems on graphs
• Computational Complexity
• Describing parameterized complexity classes
• Determinant sums for undirected Hamiltonicity
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Exact Algorithms for Maximum Independent Set
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• On the possibility of faster \textsc{SAT} algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Which problems have strongly exponential complexity?

Cited in

(6)

• scientific article; zbMATH DE number 2107051 (Why is no real title available?)
• The set cover conjecture and subgraph isomorphism with a tree pattern
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• Towards exact structural thresholds for parameterized complexity
• Tight bounds for connected odd cycle transversal parameterized by clique-width
• A note on width-parameterized SAT: an exact machine-model characterization

This page was built for publication: On the equivalence among problems of bounded width

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