2016/02/25 by Serge Gaspers, Christos H. Papadimitriou, Christos Papadimitriou +7
Computer Science · Engineering · #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Control Systems and Analysis #Optimization and Packing Problems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.07876
arxiv created 2016/02/25 · openalex publication_date 2016/02/25 · arxiv updated 2016/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It was recently shown \citeSTV 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.