ProV Logo
0
(2/2/3) -SAT problem and its application...
Ahadi, Arash...

Free

(2/2/3) -SAT problem and its applications in dominating set problems by Ahadi, Arash ( Author )
Lemonjar Open Access
N.A
04-05-2016
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 r≥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∩D=∅? As an application of (2/2/3)-SAT problem we show that for every r≥3, 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.
-
Article
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1605.01319
Share this eBook