On satisfiability problems with a linear structure

DOI10.4230/LIPICS.IPEC.2016.14zbMATH Open1398.68235arXiv1602.07876OpenAlexW2963301030MaRDI QIDQ4634397FDOQ4634397

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

Publication date: 10 April 2018

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.

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

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

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)

Cited In (12)

• Complexity of the satisfiability problem for multilinear forms over a finite field
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• STACS 2004
• Title not available (Why is that?)
• A width parameter useful for chordal and co-comparability graphs
• Title not available (Why is that?)
• Complexity Results for Linear XSAT-Problems
• On efficiently solvable cases of quantum \(k\)-SAT
• Title not available (Why is that?)
• 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)