Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP | SpringerLink
Skip to main content
Springer Nature Link
Log in

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP

  • Conference paper
  • First Online:
Theory and Applications of Satisfiability Testing -- SAT 2015 (SAT 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9340))

Abstract

We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-k-CSP. For instances with n variables and cn clauses (constraints), we give algorithms running in time \({{\mathrm{poly}}}(n)\cdot 2^{n(1-\mu )}\) for

  • \(\mu = \Omega (\frac{1}{c} )\) and polynomial space solving MAX-SAT and MAX-k-SAT,

  • \(\mu = \Omega (\frac{1}{\sqrt{c}} )\) and exponential space solving MAX-SAT and MAX-k-SAT,

  • \(\mu = \Omega (\frac{1}{ck^2} )\) and polynomial space solving MAX-k-CSP,

  • \(\mu = \Omega (\frac{1}{\sqrt{ck^3}} )\) and exponential space solving MAX-k-CSP.

The previous MAX-SAT algorithms have savings \(\mu =\Omega (\frac{1}{c^2 \log ^2 c})\) for running in polynomial space [15] and \(\mu =\Omega (\frac{1}{c \log c})\) for exponential space [5]. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with cn wires.

R. Chen—Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ ERC Grant Agreement no. 615075.

R. Santhanam—Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ ERC Grant Agreement no. 615075.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7321
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9152
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75–85. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  2. Chen, J., Kanj, I.: Improved exact algorithms for max-sat. Discrete Applied Mathematics 142(1–3), 17–27 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. In: Proceedings of the 29th Annual IEEE Conference on Computational Complexity, CCC 2014 (2014)

    Google Scholar 

  4. Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small de morgan formulas. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 165–176. Springer, Heidelberg (2014)

    Google Scholar 

  5. Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in \({{\cal O}}(2^{n})\) time. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 266–276. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Fomin, F., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1–25:32 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Gaspers, S., Sorkin, G.: A universally fastest algorithm for max 2-sat, max 2-csp, and everything in between. J. Comput. Syst. Sci. 78(1), 305–335 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Golovnev, A., Kutzkov, K.: New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. 526, 18–27 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  9. Impagliazzo, R., Nisan, N.: The effect of random restrictions on formula size. Random Structures and Algorithms 4(2), 121–134 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  10. Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October 26–29, 2013, pp. 479–488 (2013)

    Google Scholar 

  11. Koivisto, M.: Optimal 2-constraint satisfaction via sum-product algorithms. Inf. Process. Lett. 98(1), 24–28 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for demorgan formula size. In: Proceedings of the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science, pp. 588–597 (2013)

    Google Scholar 

  13. Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 194–204. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  14. Paterson, M., Zwick, U.: Shrinkage of de Morgan formulae under restriction. Random Structures and Algorithms 4(2), 135–150 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  15. Sakai, T., Seto, K., Tamaki, S.: Solving sparse instances of Max SAT via width reduction and greedy restriction. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 32–47. Springer, Heidelberg (2014)

    Google Scholar 

  16. Santhanam, R.: Fighting perebor: new and improved algorithms for formula and qbf satisfiability. In: Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, pp. 183–192 (2010)

    Google Scholar 

  17. Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms 54(1), 40–44 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Scott, A., Sorkin, G.: Linear-programming design and analysis of fast algorithms for max 2-csp. Discret. Optim. 4(3–4), 260–287 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  19. Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2–3), 357–365 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Informatics, University of Edinburgh, Edinburgh, UK

    Ruiwen Chen & Rahul Santhanam

Authors
  1. Ruiwen Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rahul Santhanam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Ruiwen Chen or Rahul Santhanam .

Editor information

Editors and Affiliations

  1. Algorithms, University of Texas, Austin, Texas, USA

    Marijn Heule

  2. Trusted Systems Research Group, Fort Meade, Texas, USA

    Sean Weaver

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Chen, R., Santhanam, R. (2015). Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. In: Heule, M., Weaver, S. (eds) Theory and Applications of Satisfiability Testing -- SAT 2015. SAT 2015. Lecture Notes in Computer Science(), vol 9340. Springer, Cham. https://doi.org/10.1007/978-3-319-24318-4_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-24318-4_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-24317-7

  • Online ISBN: 978-3-319-24318-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation