Color Structures and the Monotone Satisfiability Problem with Bounded Variable Occurrence
arXiv:2311.06563
The paper investigates a restricted monotone 3‑SAT variant where each variable appears at most k times positively and exactly once negatively, and proves that for k = 3 or 4 every instance is satisfiable, providing a linear‑time construction using a new concept called color structures.
Abstract
We study \textsc{Monotone 3-Sat-}, a restricted variant of the \textsc{Satisfiability} problem where clauses consist of three variables and are monotone (every clause contains either only unnegated or only negated variables) with up to 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 \textsc{Monotone} 3-\textsc{Sat}, Discrete Applied Mathematics 292:45--58, 2021) by proving that for~, 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 follows by a result by Tovey (A simplified NP-complete satisfiability problem, Discrete Applied Mathematics 8(1):85--89, 1984), while NP-completeness for~ was shown by Darmann and Döcker. To obtain our result, we introduce the notion of \emph{color structures} and show that a satisfying assignment can always be constructed in time, where and denote the number of negative and positive clauses of the input formula, respectively.
14 pages, 10 figures