On satisfiability problems with a linear structure

DOI10.4230/LIPICS.IPEC.2016.14MaRDI QIDQ4634397zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Sigve Hortemo Sæther, Jan Arne Telle, Christos Papadimitriou

Publication date 10 April 2018

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

zbMATH Keywords

interval graphssatisfiabilityFPT algorithms

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)

Abstract: It was recently shown cite{STV} that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite graph by omitting all edges within each partite set). Here we relax this condition in several directions: First, we show that it holds for $k$-interval bigraphs, bipartite graphs which can be converted to interval bipartite graphs by adding to each node of one side at most $k$ edges; the same result holds for the counting and the weighted maximization version of satisfiability. Second, given two linear orders, one for the variables and one for the clauses, we show how to find, in polynomial time, the smallest $k$ such that there is a $k$-interval bigraph compatible with these two orders. On the negative side we prove that, barring complexity collapses, no such extensions are possible for CSPs more general than satisfiability. We also show NP-hardness of recognizing 1-interval bigraphs.

Recommendations

• Satisfiability problems on intervals and unit intervals
• scientific article; zbMATH DE number 2177624
• Nested satisfiability
• Theory and Applications of Satisfiability Testing
• Constraint Satisfaction Problems on Intervals and Lengths

Cited in

(11)

• Complexity of the satisfiability problem for multilinear forms over a finite field
• scientific article; zbMATH DE number 2084702 (Why is no real title available?)
• scientific article; zbMATH DE number 1979549 (Why is no real title available?)
• scientific article; zbMATH DE number 5613969 (Why is no real title available?)
• STACS 2004
• scientific article; zbMATH DE number 7300404 (Why is no real title available?)
• Complexity Results for Linear XSAT-Problems
• On efficiently solvable cases of quantum \(k\)-SAT
• On efficiently solvable cases of quantum \(k\)-SAT
• scientific article; zbMATH DE number 1256705 (Why is no real title available?)
• Lower bounds on the mim-width of some graph classes

This page was built for publication: On satisfiability problems with a linear structure

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