2026-08-07T20:31:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6941 2024-03-06T10:38:48Z ddc:004 open_access

On Satisfiability Problems with a Linear Structure Gaspers, Serge Papadimitriou, Christos H. Sæther, Sigve Hortemo Telle, Jan Arne Satisfiability interval graphs FPT algorithms It was recently shown [Sæther, Telle, and Vatshelle, JAIR 54, 2015] 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 an FPT algorithm parameterized by k 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Serge Gaspers and Christos H. Papadimitriou and Sigve Hortemo Sæther and Jan Arne Telle 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.14 urn:nbn:de:0030-drops-69412 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode