2024/12/04 by Andreas Darmann, Darmann, Andreas, Janosch Döcker +3
Engineering · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2412.03395
openalex publication_date 2024/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint union of k partitions, for any fixed k ≥ 4, of the variable set into subsets of size 3, and (ii) each pair of distinct clauses shares at most one variable. Property (i) implies that each variable appears in exactly k clauses and each clause consists of exactly 3 unnegated variables. Therewith, we improve upon our earlier result (Darmann and Döcker, 2020). Complementing the hardness result for at least 4 partitions, we show that for k≤ 3 the corresponding decision problem is in P. In particular, for k∈ \1,2\, all instances that satisfy Property (i) are nae-satisfiable. By the well-known correspondence between Not-All-Equal 3-Sat and hypergraph coloring, we obtain the following corollary of our results: For k≥ 4, Bicolorability is NP-complete for linear 3-uniform k-regular hypergraphs even if the edges are given as a decomposition into k perfect matchings; with the same restrictions, for k ≤ 3 Bicolorability is in P, and for k ∈ \1,2\ all such hypergraphs are bicolorable. Finally, we deduce from a construction in the work by Pilz (Pilz, 2019) that every instance of Positive Planar Not-All-Equal Sat with at least three distinct variables per clause is nae-satisfiable. Hence, when restricted to instances with a planar incidence graph, each of the above variants of Not-All-Equal 3-Sat turns into a trivial decision problem.