"On variable-weighted exact satisfiability problems"
Technical report by Stefan Porschen, available as BibTeX Source, postscript file, compressed postscript file and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Speckenmeyer
Preprint Key:	zaik2006-526
Keywords:	combinatorial optimization, counting problem, exact algorithm, maximum weight independent set, NP-completeness, perfect matching, set partition, weighted exact satisfiability
MSC codes:	03B05, 05C85, 68Q25
This technical report has 36 pages, was written in August 2006, it has not been published. (accepted for publication in Annals Math. Artif. Intelligence)
Abstract:	We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(|C|2^{0.2441n}) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n^2cdot |C|+2^{0.40567n}) time. In recent years only the unweighted counterparts of these problems have been studied cite{dahl,dahl2,porschen}.