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

DOI10.1016/j.dam.2020.12.010OpenAlexW3120847125MaRDI QIDQ2223685

Janosch Döcker, Andreas Darmann

Publication date: 1 February 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.12.010

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items

On the approximation hardness of geodetic set and its variants ⋮ Complexity results for two kinds of colored disconnections of graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Two-segmented channel routing is strong NP-complete
• On the parameterized complexity of \((k,s)\)-SAT
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• The Lovász Local Lemma and Satisfiability
• Planar Formulae and Their Uses
• Complexity of automaton identification from given data
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Theory and Applications of Satisfiability Testing
• The complexity of theorem-proving procedures