Porschen, Stefan, Schmidt, Tatjana, Speckenmeyer, Ewald and Wotzlaw, Andreas (2014). XSAT and NAE-SAT of linear CNF classes. Discret Appl. Math., 167. S. 1 - 15. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6771
Full text not available from this repository.Abstract
XSAT and NAE-SAT are important variants of the propositional satisfiability problem (SAT). XSAT contains all CNF formulas that can be satisfied by setting exactly one literal in each clause to 1, whereas NAE-SAT requires satisfying truth assignments not setting all literals equally in any clause. Both variants are studied here regarding their computational complexity of linear CNF formulas, whose clauses are allowed to have at most one variable in common. We prove that both variants remain NP-complete for (monotone) linear formulas, yielding the conclusion that also bicolorability of linear hypergraphs is NP-complete. The reduction used gives rise to the complexity investigations of several monotone linear subclasses of both variants that are parameterized by the size of clauses, or by the number of occurrences of variables. For particular values of those parameters, we are able to show the NP-completeness of XSAT and NAE-SAT, though we cannot provide a complete treatment. Finally, we focus on exact linear formulas, where clauses intersect pairwise, and for which SAT is known to be polynomial-time solvable. Here, we prove NP-completeness of XSAT for exact linear formulas. If in addition the clauses are required to be of uniform length, we show that both XSAT and NAE-SAT are decidable in polynomial time, what even holds for their counting versions. (C) 2013 Elsevier B.V. All rights reserved.
| Item Type: | Journal Article | ||||||||||||||||||||
| Creators: |
|
||||||||||||||||||||
| URN: | urn:nbn:de:hbz:38-440561 | ||||||||||||||||||||
| DOI: | 10.1016/j.dam.2013.10.030 | ||||||||||||||||||||
| Journal or Publication Title: | Discret Appl. Math. | ||||||||||||||||||||
| Volume: | 167 | ||||||||||||||||||||
| Page Range: | S. 1 - 15 | ||||||||||||||||||||
| Date: | 2014 | ||||||||||||||||||||
| Publisher: | ELSEVIER SCIENCE BV | ||||||||||||||||||||
| Place of Publication: | AMSTERDAM | ||||||||||||||||||||
| ISSN: | 1872-6771 | ||||||||||||||||||||
| Language: | English | ||||||||||||||||||||
| Faculty: | Unspecified | ||||||||||||||||||||
| Divisions: | Unspecified | ||||||||||||||||||||
| Subjects: | no entry | ||||||||||||||||||||
| Uncontrolled Keywords: |
|
||||||||||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/44056 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
 |
View Item |