Document Open Access Logo

A General Framework for Enumerating Equivalence Classes of Solutions

Authors Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.80.pdf
  • Filesize: 0.73 MB
  • 14 pages

Document Identifiers

Author Details

Yishu Wang
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
Arnaud Mary
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
Marie-France Sagot
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
Blerina Sinaimeri
  • Luiss University, Rome, Italy
  • ERABLE team, Inria Grenoble Rhône-Alpes, Villeurbanne, France

Cite As Get BibTex

Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. A General Framework for Enumerating Equivalence Classes of Solutions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.80

Abstract

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic programming
  • Mathematics of computing → Graph enumeration
  • Theory of computation → Backtracking
Keywords
  • Enumeration algorithms
  • Equivalence relation
  • Dynamic programming

Metrics

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

Related Versions

References

  1. Steen A. Andersson, David Madigan, and Michael D. Perlman. A characterization of markov equivalence classes for acyclic digraphs. Annals of Statistics, 25(2):505-541, April 1997. URL: https://doi.org/10.7916/D8280JSB.
  2. Albert Angel and Nick Koudas. Efficient diversity-aware search. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD '11, page 781–792, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1989323.1989405.
  3. Mukul S. Bansal, Eric J. Alm, and Manolis Kellis. Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics, 28(12):i283-i291, 2012. URL: https://doi.org/10.1093/bioinformatics/bts225.
  4. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61–63, January 1962. URL: https://doi.org/10.1145/321105.321111.
  5. Richard Bellman. Dynamic Programming. Dover Books on Computer Science. Dover Publications, 2013. Google Scholar
  6. Umberto Bertele and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, Inc., USA, 1972. Google Scholar
  7. Anselm Blumer, Janet A. Blumer, David H. Haussler, Ross M. McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. Journal of the ACM, 34(3):578–595, July 1987. URL: https://doi.org/10.1145/28869.28873.
  8. Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In Timo Lepistö and Arto Salomaa, editors, Automata, Languages and Programming, pages 105-118, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-19488-6_110.
  9. Pierre E. Bonzon. Necessary and sufficient conditions for dynamic programming of combinatorial type. Journal of the ACM, 17:675-682, 1970. URL: https://doi.org/10.1145/321607.321616.
  10. Marília D.V. Braga, Marie-France Sagot, Celine Scornavacca, and Eric Tannier. Exploring the solution space of sorting by reversals, with experiments and an application to evolution. IEEE/ACM transactions on computational biology and bioinformatics, 5 3:348-56, 2008. URL: https://doi.org/10.1109/TCBB.2008.16.
  11. Joshua Buresh-Oppenheim, Sashka Davis, and Russell Impagliazzo. A stronger model of dynamic programming algorithms. Algorithmica, 60:938-968, August 2011. URL: https://doi.org/10.1007/s00453-009-9385-1.
  12. Rina Dechter and Robert Mateescu. And/or search spaces for graphical models. Artificial Intelligence, 171(2):73-106, 2007. URL: https://doi.org/10.1016/j.artint.2006.11.003.
  13. Beatrice Donati, Christian Baudet, Blerina Sinaimeri, Pierluigi Crescenzi, and Marie-France Sagot. Eucalypt: efficient tree reconciliation enumerator. Algorithms for Molecular Biology, 10(1):3, 2015. URL: https://doi.org/10.1186/s13015-014-0031-3.
  14. Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Pictorial structures for object recognition. International Journal of Computer Vision, 61(1):55–79, January 2005. URL: https://doi.org/10.1023/B:VISI.0000042934.15159.49.
  15. Henning Fernau, Petr A. Golovach, and Marie-France Sagot. Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421). Dagstuhl Reports, 8(10):63-86, 2019. URL: https://doi.org/10.4230/DagRep.8.10.63.
  16. Stefania Gnesi, Ugo Montanari, and Alberto Martelli. Dynamic programming as graph searching: An algebraic approach. Journal of the ACM, 28(4):737–751, 1981. URL: https://doi.org/10.1145/322276.322285.
  17. William K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497-1514, 1980. URL: https://doi.org/10.1109/PROC.1980.11899.
  18. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196-210, 1962. URL: https://doi.org/10.1137/0110015.
  19. Paul Helman. A common schema for dynamic programming and branch and bound algorithms. Journal of the ACM, 36(1):97–128, January 1989. URL: https://doi.org/10.1145/58562.59304.
  20. Toshihide Ibaraki. Classes of discrete optimization problems and their decision problems. Journal of Computer and System Sciences, 8(1):84-116, 1974. URL: https://doi.org/10.1016/S0022-0000(74)80024-3.
  21. Richard M. Karp and Michael Held. Finite-state processes and dynamic programming. SIAM Journal on Applied Mathematics, 15(3):693-718, 1967. URL: https://doi.org/10.1137/0115060.
  22. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Basic Algorithmic Concepts, pages 15-42. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-540-24777-7_2.
  23. Alberto Martelli and Ugo Montanari. Optimizing decision trees through heuristically guided search. Communications of the ACM, 21(12):1025–1039, 1978. URL: https://doi.org/10.1145/359657.359664.
  24. Cristian Molinaro, Amy Sliva, and Vs S. Subrahmanian. Super-solutions: Succinctly representing solutions in abductive annotated probabilistic temporal logic. ACM Transactions on Computational Logic, 15(3), July 2014. URL: https://doi.org/10.1145/2627354.
  25. Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 9:415, 2015. URL: https://doi.org/10.3934/amc.2015.9.415.
  26. Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Efficient computation of substring equivalence classes with suffix arrays. In Bin Ma and Kaizhong Zhang, editors, Combinatorial Pattern Matching, pages 340-351, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/s00453-016-0178-z.
  27. Nils J. Nilsson. Principles of Artificial Intelligence. Springer-Verlag Berlin Heidelberg, Tioga, Palo Alto, CA, 1982. Google Scholar
  28. Roderic D. M. Page. Tangled trees: phylogeny, cospeciation, and coevolution. The University of Chicago Press, 2003. Google Scholar
  29. Fred S. Roberts. T-colorings of graphs: recent results and open problems. Discrete Mathematics, 93(2):229-245, 1991. URL: https://doi.org/10.1016/0012-365X(91)90258-4.
  30. Lior Rokach and Oded Z. Maimon. Data Mining with Decision Trees: Theory and Applications. Series in machine perception and artificial intelligence. World Scientific, 2008. URL: https://doi.org/10.1142/9097.
  31. David Sankoff. Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics, 28(1):35-42, 1975. URL: https://doi.org/10.1137/0128004.
  32. Barry A. Tesman. List t-colorings of graphs. Discrete Applied Mathematics, 45(3):277-289, 1993. URL: https://doi.org/10.1016/0166-218X(93)90015-G.
  33. Olga Veksler. Stereo correspondence by dynamic programming on a tree. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), volume 2, pages 384-390, 2005. URL: https://doi.org/10.1109/CVPR.2005.334.
  34. Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168–173, January 1974. URL: https://doi.org/10.1145/321796.321811.
  35. Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. Capybara: equivalence class enumeration of cophylogeny event-based reconciliations. Bioinformatics, 36(14):4197-4199, 2020. URL: https://doi.org/10.1093/bioinformatics/btaa498.
  36. Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. A general framework for enumerating equivalence classes of solutions, 2021. URL: http://arxiv.org/abs/2004.12143.
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 About DROPS Imprint Privacy Contact