On the parameterized complexity of \((k,s)\)-SAT

DOI10.1016/j.ipl.2018.11.005zbMath1478.68105OpenAlexW2900560989MaRDI QIDQ1711421

Stefan Szeider, Daniël Paulusma

Publication date: 18 January 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/26874/1/26874.pdf

zbMATH Keywords

computational complexitysatisfiabilityfixed-parameter tractability\((k,s)\)-formulas

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (1)

On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}

Cites Work

• Unnamed Item
• Unnamed Item
• Disproof of the neighborhood conjecture with implications to SAT
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• A simplified NP-complete satisfiability problem
• Computational complexity of some restricted instances of 3-SAT
• Solving satisfiability in less than \(2^ n\) steps
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Reducibility among Combinatorial Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On the parameterized complexity of \((k,s)\)-SAT