Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 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 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 NP-complete. We call this problem (2/2/3)-SAT. For an r-regular graph G=(V,E) with r3, 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 TD=? As an application of (2/2/3)-SAT problem we show that for every r3, this problem is 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 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 1163 times.
    This article's PDF has been downloaded 490 times.