Arash Ahadi ; Ali Dehghan - $(2/2/3)$-SAT problem and its applications in dominating set problems

dmtcs:1464 - Discrete Mathematics & Theoretical Computer Science, August 12, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-9
$(2/2/3)$-SAT problem and its applications in dominating set problemsArticle

Authors: Arash Ahadi ; Ali Dehghan

    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\geq 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\geq 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.


    Volume: vol. 21 no. 4
    Section: Graph Theory
    Published on: August 12, 2019
    Accepted on: August 5, 2019
    Submitted on: May 5, 2016
    Keywords: Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 1127 times.
    This article's PDF has been downloaded 416 times.