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:
CreatorsEmailORCIDORCID Put Code
Porschen, StefanUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schmidt, TatjanaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Speckenmeyer, EwaldUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Wotzlaw, AndreasUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
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:
KeywordsLanguage
SATISFIABILITY; ALGORITHMS; FORMULAS; COMPLEXITYMultiple languages
Mathematics, AppliedMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/44056

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item