Parameterized and subexponential-time complexity of satisfiability problems and applications

DOI10.1016/J.TCS.2015.08.029MaRDI QIDQ896108zbMATH OpenOpenAlexFDO

Authors Iyad Kanj, Stefan Szeider

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.08.029

zbMATH Keywords

parameterized complexitycircuit satisfiabilitysubexponential-time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Recommendations

• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized complexity of weighted satisfiability problems
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• Parameterized complexity and subexponential-time computability
• Tight lower bounds for certain parameterized NP-hard problems

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• An improved deterministic local search algorithm for 3-SAT
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• Introduction to algorithms
• On miniaturized problems in parameterized complexity theory
• On parameterized exponential time complexity
• On the complexity of \(k\)-SAT
• On the existence of subexponential parameterized algorithms
• On the possibility of faster \textsc{SAT} algorithms
• Optimization, approximation, and complexity classes
• Parameterized complexity and subexponential-time computability
• Parametrized complexity theory.
• STACS 2004
• Strong computational lower bounds via parameterized complexity
• Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• Tight lower bounds for certain parameterized NP-hard problems
• Vertex cover: Further observations and further improvements
• Which problems have strongly exponential complexity?
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(12)

• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Polynomial-average-time satisfiability problems
• Solving QSAT in sublinear depth
• A perspective on certain polynomial-time solvable classes of satisfiability
• Tight lower bounds for certain parameterized NP-hard problems
• Solving the resolution-free SAT problem by submodel propagation in linear time
• On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
• Mathematical Foundations of Computer Science 2005
• On the existence of subexponential parameterized algorithms
• Parameterized complexity and subexponential-time computability
• On O(Tlog T) reduction from RAM computations to satisfiability
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach

This page was built for publication: Parameterized and subexponential-time complexity of satisfiability problems and applications

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