License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.90
URN: urn:nbn:de:0030-drops-55747
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5574/
Go to the corresponding LIPIcs Volume Portal

Sakai, Takayuki ; Seto, Kazuhisa ; Tamaki, Suguru ; Teruyama, Junichi

Improved Exact Algorithms for Mildly Sparse Instances of Max SAT

pdf-format:
11.pdf (0.5 MB)

Abstract

We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form O(2^{(1-mu(c))n}) for instances with n variables and m=cn clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with mu(c)=1/O(c * log(c)) due to Dantsin and Wolpert [SAT 2006], a randomized polynomial space algorithm with mu(c)=1/O(c * log^3(c)) and a deterministic polynomial space algorithm with mu(c)=1/O(c^2 * log^2(c)) due to Sakai, Seto and Tamaki [Theory Comput. Syst., 2015]. Our first result is a deterministic polynomial space algorithm with mu(c)=1/O(c * log(c)) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2^n only if m=O(n^2).

Our second results are deterministic exponential space algorithms for Max SAT with mu(c)=1/O((c * log(c))^{2/3}) and for Max 3-SAT with mu(c)=1/O(c^{1/2}) that run super-polynomially faster than 2^n when m=o(n^{5/2}/log^{5/2}(n)) and m=o(n^3/log^2(n)) respectively.

BibTeX - Entry

@InProceedings{sakai_et_al:LIPIcs:2015:5574,
  author =	{Takayuki Sakai and Kazuhisa Seto and Suguru Tamaki and Junichi Teruyama},
  title =	{{Improved Exact Algorithms for Mildly Sparse Instances of Max SAT}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{90--101},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5574},
  URN =		{urn:nbn:de:0030-drops-55747},
  doi =		{10.4230/LIPIcs.IPEC.2015.90},
  annote =	{Keywords: maximum satisfiability, weighted, polynomial space, exponential space}
}

Keywords: maximum satisfiability, weighted, polynomial space, exponential space
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI