Document Open Access Logo

A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT

Authors Gordon Hoi, Sanjay Jain, Frank Stephan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.17.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Gordon Hoi
  • School of Computing, National University of Singapore, Singapore 117417, Republic of Singapore
Sanjay Jain
  • School of Computing, National University of Singapore, Singapore 117417, Republic of Singapore
Frank Stephan
  • Dept. of Mathematics, National University of Singapore, Singapore 119076, Republic of Singapore
  • School of Computing, National University of Singapore, Singapore 117417, Republic of Singapore

Funding

  • Jain, Sanjay: supported in part by the NUS grant C-252-000-087-001 and by Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2016-T2-1-019 / R1467-000-234-112.
  • Stephan, Frank: supported in part by the Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2016-T2-1-019 / R1467-000-234-112.

Cite AsGet BibTex

Gordon Hoi, Sanjay Jain, and Frank Stephan. A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.17

Abstract

X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A related question is to determine the maximal Hamming distance between two solutions of the instance. Dahllöf provided an algorithm for Maximum Hamming Distance XSAT, which is more complicated than the same problem for X3SAT, with a runtime of O(1.8348^n); Fu, Zhou and Yin considered Maximum Hamming Distance for X3SAT and found for this problem an algorithm with runtime O(1.6760^n). In this paper, we propose an algorithm in O(1.3298^n) time to solve the Max Hamming Distance X3SAT problem; the algorithm actually counts for each k the number of pairs of solutions which have Hamming Distance k.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Design and analysis of algorithms
Keywords
  • X3SAT Problem
  • Maximum Hamming Distance of Solutions
  • Exponential Time Algorithms
  • DPLL Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Burkhard Monien and Robert Preis. Upper bounds on the bisection width of 3- and 4-regular graphs. Journal of Discrete Algorithms, 4(3):475-498, 2006. Google Scholar
  2. David Eppstein. Small maximal independent sets and faster exact graph coloring. Proceedings of the Seventh Workshop on Algorithms and Data Structures, Springer Lecture Notes in Computer Science, 2125:462-470, 2001. Google Scholar
  3. David Eppstein. Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Transactions on Algorithms, 2(4):492-509, 2006. Google Scholar
  4. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science, EATCS, Springer, Berlin, Heidelberg, 2010. Google Scholar
  5. Serge Gaspers. Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Müller, 2010. Google Scholar
  6. Serge Gaspers and Gregory B. Sorkin. Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets. ACM Transactions on Algorithms (TALG), 13(4):44:1-44:36, 2017. Google Scholar
  7. Gordon Hoi and Frank Stephan. Measure and conquer for Max Hamming Distance XSAT. International Symposium on Algorithms and Computation, ISAAC 2019, LIPIcs, 149:18:1-18:20, 2019. Google Scholar
  8. Gordon Hoi, Sanjay Jain and Frank Stephan. A fast exponential time algorithm for Max Hamming X3SAT. arXiv, 2019. Technical Report version of this paper. URL: http://arxiv.org/abs/1910.01293.
  9. Linlu Fu, Junping Zhou and Minghao Yin. Worst case upper bound for the maximum Hamming distance X3SAT problem. Journal of Frontiers of Computer Science and Technology, 6(7):664-671, 2012. Google Scholar
  10. Magnus Wahlström. Algorithms, measures and upper bounds for satisfiability and related problems. PhD thesis, Department of Computer and Information Science, Linköping University, 2007. Google Scholar
  11. Martin Davis and Hilary Putnam. A computing procedure for quantification theory. Journal of the ACM, 7(3):201-215, 1960. Google Scholar
  12. Martin Davis, George Logemann and Donald W. Loveland. A machine program for theorem proving. Communications of the ACM, 5(7):394-397, 1962. Google Scholar
  13. Ola Angelsmark and Johan Thapper. Algorithms for the maximum Hamming distance problem. Recent Advances in Constraints, International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 204, Springer Lecture Notes in Computer Science, 3419:128-141, 2004. Google Scholar
  14. Oliver Kullmann. New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science, 223(1-2):1-72, 1999. Google Scholar
  15. Pierluigi Crescenzi and Gianluca Rossi. On the Hamming distance of constraint satisfaction problems. Theoretical Computer Science, 288(1):85-100, 2002. Google Scholar
  16. Richard Wesley Hamming. Error detecting and error correcting codes. Bell System Technical Journal, 29(2):147-160, 1950. Google Scholar
  17. Satya Gautam Vadlamudi and Subbarao Kambhampati. A combinatorial search perspective on diverse solution generation. Thirtieth AAAI Conference on Artificial Intelligence, pages 776-783, 2016. Google Scholar
  18. Vilhelm Dahllöf. Algorithms for Max Hamming Exact Satisfiability. International Symposium on Algorithms and Computation, ISAAC 2005, Springer Lecture Notes in Computer Science, 3827:829-383, 2005. Google Scholar
  19. Vilhelm Dahllöf. Exact Algorithms for Exact Satisfiability Problems. PhD thesis, Department of Computer and Information Science, Linköping University, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact