On variable-weighted exact satisfiability problems

Porschen, Stefan (2007) On variable-weighted exact satisfiability problems.
Published in: Annals of mathematics and artificial intelligence Vol. 51 (1). pp. 27-54.


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}.

Download: [img] Postscript - Preprinted Version
Download (298kB) | Preview
Download: [img] PDF - Preprinted Version
Download (369kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-526
Depositing User: Stefan Porschen
Date Deposited: 19 Apr 2007 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/526