Color Structures and the Monotone Satisfiability Problem with Bounded Variable Occurrence
For researchers in computational complexity, this completes the classification of a restricted SAT variant, but the result is incremental as it closes a known gap.
The paper resolves a challenge by proving that Monotone 3-SAT with bounded variable occurrence (k=3,4) is always satisfiable, closing the gap in a dichotomy theorem. The result shows triviality for k≤4 and NP-completeness for k≥5.
We study \textsc{Monotone 3-Sat-$(\leq k,1)$}, 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 $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 \textsc{Monotone} 3-\textsc{Sat}, Discrete Applied Mathematics 292:45--58, 2021) by proving that for~$k\in \{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\in \{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\geq 5$ 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 $\mathcal{O}(n \cdot m)$ time, where $n$ and $m$ denote the number of negative and positive clauses of the input formula, respectively.