Efficient Enumeration of Solutions Produced by Closure Operations

Authors Arnaud Mary, Yann Strozecki



PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.52.pdf
  • Filesize: 0.65 MB
  • 13 pages

Document Identifiers

Author Details

Arnaud Mary
Yann Strozecki

Cite AsGet BibTex

Arnaud Mary and Yann Strozecki. Efficient Enumeration of Solutions Produced by Closure Operations. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.52

Abstract

In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure by polymorphisms of a boolean relation with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations" (e.g. by union, intersection, difference, symmetric difference ...). To do so, we prove that for any set of operations F, one can decide in polynomial time whether an element belongs to the closure by F of a family of sets. When the relation is over a domain larger than two elements, we prove that our generic enumeration method fails, since the associated decision problem is NP-hard.
Keywords
  • enumeration
  • set saturation
  • polynomial delay
  • Post’s lattice

Metrics

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

References

  1. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1):21-46, 1996. Google Scholar
  2. Kirby A Baker and Alden F Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Mathematische Zeitschrift, 143(2):165-174, 1975. Google Scholar
  3. Andrei A Bulatov, Víctor Dalmau, Martin Grohe, and Dániel Marx. Enumerating homomorphisms. Journal of Computer and System Sciences, 78(2):638-650, 2012. Google Scholar
  4. Florent Capelli, Arnaud Durand, and Yann Strozecki. A note on polynomial delay and incremental delay, 2015. URL: http://www.prism.uvsq.fr/~ystr.
  5. Nadia Creignou and Jean-Jacques Hébrard. On generating all solutions of generalized satisfiability problems. Informatique théorique et applications, 31(6):499-511, 1997. Google Scholar
  6. Jörg Flum and Martin Grohe. Parameterized complexity theory, 2006. Google Scholar
  7. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 1988. Google Scholar
  8. Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. On the complexity of some enumeration problems for matroids. SIAM Journal on Discrete Mathematics, 19(4):966-984, 2005. Google Scholar
  9. Donald E Knuth. Combinatorial Algorithms, Part 1, volume 4A of The Art of Computer Programming, 2011. Google Scholar
  10. Emil Leon Post. The two-valued iterative systems of mathematical logic. Princeton University Press, 1941. Google Scholar
  11. Robert C Read and Robert E Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237-252, 1975. Google Scholar
  12. Steffen Reith and Heribert Vollmer. Optimal satisfiability for propositional calculi and constraint satisfaction problems. Information and Computation, 186(1):1-19, 2003. Google Scholar
  13. Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226. ACM, 1978. Google Scholar
  14. Yann Strozecki. Enumeration complexity and matroid decomposition. PhD thesis, Université Paris Diderot - Paris 7, 2010. Google Scholar
  15. Yann Strozecki. On enumerating monomials and other combinatorial structures by polynomial interpolation. Theory Comput. Syst., 53(4):532-568, 2013. 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