LIPIcs.STACS.2016.52.pdf
- Filesize: 0.65 MB
- 13 pages
Document
Efficient Enumeration of Solutions Produced by Closure Operations
Authors
-
Part of:
Volume:
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-02-16
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
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)
0PDF Downloads
References
-
David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1):21-46, 1996.
-
Kirby A Baker and Alden F Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Mathematische Zeitschrift, 143(2):165-174, 1975.
-
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.
- Florent Capelli, Arnaud Durand, and Yann Strozecki. A note on polynomial delay and incremental delay, 2015. URL: http://www.prism.uvsq.fr/~ystr.
-
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.
-
Jörg Flum and Martin Grohe. Parameterized complexity theory, 2006.
-
David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 1988.
-
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.
-
Donald E Knuth. Combinatorial Algorithms, Part 1, volume 4A of The Art of Computer Programming, 2011.
-
Emil Leon Post. The two-valued iterative systems of mathematical logic. Princeton University Press, 1941.
-
Robert C Read and Robert E Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237-252, 1975.
-
Steffen Reith and Heribert Vollmer. Optimal satisfiability for propositional calculi and constraint satisfaction problems. Information and Computation, 186(1):1-19, 2003.
-
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.
-
Yann Strozecki. Enumeration complexity and matroid decomposition. PhD thesis, Université Paris Diderot - Paris 7, 2010.
-
Yann Strozecki. On enumerating monomials and other combinatorial structures by polynomial interpolation. Theory Comput. Syst., 53(4):532-568, 2013.