$(2/2/3)$-SAT problem and its applications in dominating set problems

Abstract

The satisfiability problem is known to be $\mathbf{NP}$-complete in general and for many restricted cases. One way to restrict instances of $k$-SAT is to limit the number of times a variable can be occurred. It was shown that for an instance of 4-SAT with the property that every variable appears in exactly 4 clauses (2 times negated and 2 times not negated), determining whether there is an assignment for variables such that every clause contains exactly two true variables and two false variables is $\mathbf{NP}$-complete. In this work, we show that deciding the satisfiability of 3-SAT with the property that every variable appears in exactly four clauses (two times negated and two times not negated), and each clause contains at least two distinct variables is $\mathbf{NP}$-complete. We call this problem $(2/2/3)$-SAT. For an $r$-regular graph $G=(V,E)$ with $r\ge 3$, it was asked in [Discrete Appl. Math., 160(15):2142--2146, 2012] to determine whether for a given independent set $T$ there is an independent dominating set $D$ that dominates $T$ such that $T\cap D=\varnothing$? As an application of $(2/2/3)$-SAT problem we show that for every $r\ge 3$, this problem is $\mathbf{NP}$-complete. Among other results, we study the relationship between 1-perfect codes and the incidence coloring of graphs and as another application of our complexity results, we prove that for a given cubic graph $G$ deciding whether $G$ is 4-incidence colorable is $\mathbf{NP}$-complete.

References in corpus (1)

• Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number