2023/11/11 by Hannah Van Santvliet, Ronald de Haan, Van Santvliet, Hannah +1
Computer Science · Engineering · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2311.06563
openalex publication_date 2023/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study Monotone 3-Sat-(≤ k,1), a restricted variant of the Satisfiability problem where clauses consist of three variables and are monotone (every clause contains either only unnegated or only negated variables) with up to k positive and exactly one negative occurrence per variable in the formula. We resolve a challenge posed by Darmann and Döcker (On simplified NP-complete variants of Monotone 3-Sat, Discrete Applied Mathematics 292:45--58, 2021) by proving that for~k∈ \3,4\, the problem is trivial in the sense that every instance satisfying the given restrictions is satisfiable. This result closes the remaining gap in a dichotomy theorem: Triviality for k∈ \1,2\ follows by a result by Tovey (A simplified NP-complete satisfiability problem, Discrete Applied Mathematics 8(1):85--89, 1984), while NP-completeness for~k≥ 5 was shown by Darmann and Döcker. To obtain our result, we introduce the notion of color structures and show that a satisfying assignment can always be constructed in O(n ⋅ m) time, where n and m denote the number of negative and positive clauses of the input formula, respectively.