Document Open Access Logo

Enumerating Maximal Induced Subgraphs

Author Yixin Cao

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.31.pdf
  • Filesize: 0.68 MB
  • 13 pages

Document Identifiers

Author Details

Yixin Cao
  • Department of Computing, Hong Kong Polytechnic University, Hong Kong, China

Funding

Supported in part by the Hong Kong Research Grants Council (RGC) under grant 15221420 and the National Natural Science Foundation of China (NSFC) under grant 61972330.

Cite AsGet BibTex

Yixin Cao. Enumerating Maximal Induced Subgraphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.31

Abstract

Given a graph G, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of G that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has been intensively studied, enumeration algorithms were only known for a few simple graph classes, e.g., independent sets, cliques, and forests, until very recently [Conte and Uno, STOC 2019]. There is also a connected variation of this problem, where one is concerned with only those induced subgraphs that are connected. We introduce two new approaches, which enable us to develop algorithms that solve both variations for a number of important graph classes. A general technique that has been proven very powerful in enumeration algorithms is to build a solution map, i.e., a multiple digraph on all the solutions of the problem, and the key of this approach is to make the solution map strongly connected, so that a simple traversal of the solution map solves the problem. First, we introduce retaliation-free paths to certify strong connectedness of the solution map we build. Second, generalizing the idea of Cohen, Kimelfeld, and Sagiv [JCSS 2008], we introduce an apparently very restricted version of the maximal (connected) induced subgraphs problem, and show that it is equivalent to the original problem in terms of solvability in incremental polynomial time. Moreover, we give reductions between the two variations, so that it suffices to solve one of the variations for each class we study. Our work also leads to direct and simpler proofs of several important known results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • enumeration algorithm
  • hereditary graph class
  • maximal induced subgraph

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Transactions on Algorithms, 15(1):11:1-11:28, 2019. URL: https://doi.org/10.1145/3284356.
  2. Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Interval vertex deletion admits a polynomial kernel. In Timothy M. Chan, editor, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1711-1730. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.103.
  3. E. A. Akkoyunlu. The enumeration of maximal cliques of large graphs. SIAM Journal on Computing, 2(1):1-6, 1973. URL: https://doi.org/10.1137/0202001.
  4. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1-3):21-46, 1996. URL: https://doi.org/10.1016/0166-218X(95)00026-N.
  5. Jan C. Bioch and Toshihide Ibaraki. Complexity of identification and dualization of positive boolean functions. Information and Computation, 123(1):50-63, 1995. URL: https://doi.org/10.1006/inco.1995.1157.
  6. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39(2):546-563, 2009. URL: https://doi.org/10.1137/070683933.
  7. Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Largest chordal and interval subgraphs faster than 2ⁿ. Algorithmica, 76(2):569-594, 2016. URL: https://doi.org/10.1007/s00453-015-0054-2.
  8. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using P Q-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
  9. Jesper Makholm Byskov. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 32(6):547-556, 2004. URL: https://doi.org/10.1016/j.orl.2004.03.002.
  10. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
  11. Yixin Cao. Linear recognition of almost interval graphs. In Robert Krauthgamer, editor, Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096-1115. SIAM, 2016. Full version available at https://arxiv.org/abs/1403.1515. URL: https://doi.org/10.1137/1.9781611974331.ch77.
  12. Yixin Cao. Unit interval editing is fixed-parameter tractable. Information and Computation, 253:109-126, 2017. URL: https://doi.org/10.1016/j.ic.2017.01.008.
  13. Yixin Cao. Recognizing (unit) interval graphs by zigzag graph searches. In Hung Viet Le and Valerie King, editors, Proceedings of the 4th SIAM Symposium on Simplicity in Algorithms (SOSA), pages 92-106. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976496.11.
  14. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms, 11(3):21:1-21:35, 2015. URL: https://doi.org/10.1145/2629595.
  15. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. URL: https://doi.org/10.1007/s00453-015-0014-x.
  16. Florent Capelli and Yann Strozecki. Incremental delay enumeration: Space and time. Discrete Applied Mathematics, 268:179-190, 2019. URL: https://doi.org/10.1016/j.dam.2018.06.038.
  17. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210-223, 1985. URL: https://doi.org/10.1137/0214017.
  18. Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. Journal of Computer and System Sciences, 74(7):1147-1159, 2008. URL: https://doi.org/10.1016/j.jcss.2008.04.003.
  19. Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, and Luca Versari. Proximity search for maximal subgraph enumeration. SIAM Journal on Computing, 51(5):1580-1625, 2022. URL: https://doi.org/10.1137/20m1375048.
  20. Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. Listing maximal subgraphs satisfying strongly accessible properties. SIAM Journal on Discrete Mathematics, 33(2):587-613, 2019. URL: https://doi.org/10.1137/17M1152206.
  21. Alessio Conte and Takeaki Uno. New polynomial delay bounds for maximal subgraph enumeration by proximity search. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 1179-1190. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316402.
  22. Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. A complexity theory for hard enumeration problems. Discrete Applied Mathematics, 268:191-209, 2019. URL: https://doi.org/10.1016/j.dam.2019.02.025.
  23. Vânia M. F. Dias, Celina M. H. de Figueiredo, and Jayme Luiz Szwarcfiter. Generating bicliques of a graph in lexicographic order. Theoretical Computer Science, 337(1-3):240-248, 2005. URL: https://doi.org/10.1016/j.tcs.2005.01.014.
  24. Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278-1304, 1995. URL: https://doi.org/10.1137/S0097539793250299.
  25. Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey. Discrete Applied Mathematics, 156(11):2035-2049, 2008. URL: https://doi.org/10.1016/j.dam.2007.04.017.
  26. David Eppstein. Finding the k shortest paths. SIAM Journal on Computing, 28(2):652-673, 1998. URL: https://doi.org/10.1137/S0097539795290477.
  27. David Eppstein. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl., 7(2):131-140, 2003. URL: https://doi.org/10.7155/jgaa.00064.
  28. Henning Fernau. Edge dominating set: Efficient enumeration-based exact algorithms. In Hans L. Bodlaender and Michael A. Langston, editors, Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC), volume 4169 of LNCS, pages 142-153. Springer, 2006. URL: https://doi.org/10.1007/11847250_13.
  29. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. Journal of the ACM, 66(2):8:1-8:23, 2019. URL: https://doi.org/10.1145/3284176.
  30. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
  31. Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21(3):618-628, 1996. URL: https://doi.org/10.1006/jagm.1996.0062.
  32. Delbert R. Fulkerson and Oliver A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3):835-855, 1965. URL: https://doi.org/10.2140/pjm.1965.15.835.
  33. Alain Gély, Lhouari Nourine, and Bachir Sadi. Enumeration aspects of maximal cliques and bicliques. Discrete Applied Mathematics, 157(7):1447-1459, 2009. URL: https://doi.org/10.1016/j.dam.2008.10.010.
  34. Wen-Lian Hsu. O(m⋅ n) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM Journal on Computing, 24(3):411-439, 1995. URL: https://doi.org/10.1137/S0097539793260726.
  35. Wen-Lian Hsu and Tze-Heng Ma. Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM Journal on Computing, 28(3):1004-1020, 1999. URL: https://doi.org/10.1137/S0097539792224814.
  36. Bart M. P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. In Philip N. Klein, editor, Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1399-1418. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.91.
  37. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 1988. URL: https://doi.org/10.1016/0020-0190(88)90065-8.
  38. Eugene L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66-67, 1976. URL: https://doi.org/10.1016/0020-0190(76)90065-X.
  39. Eugene L. Lawler, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM Journal on Computing, 9(3):558-565, 1980. URL: https://doi.org/10.1137/0209042.
  40. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  41. Daniel Lokshtanov. Wheel-free deletion is W[2]-hard. In Martin Grohe and Rolf Niedermeier, editors, Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC), volume 5018 of LNCS, pages 141-147, New York, 2008. Springer. URL: https://doi.org/10.1007/978-3-540-79723-4_14.
  42. Carsten Lund and Mihalis Yannakakis. The approximation of maximum subgraph problems. In Andrzej Lingas, Rolf G. Karlsson, and Svante Carlsson, editors, Automata, Languages and Programming (ICALP), volume 700 of LNCS, pages 40-51. Springer, 1993. URL: https://doi.org/10.1007/3-540-56939-1_60.
  43. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Torben Hagerup and Jyrki Katajainen, editors, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, SWAT 2004, volume 3111 of LNCS, pages 260-272. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27810-8_23.
  44. Andrea Marino. Analysis and Enumeration: Algorithms for Biological Graphs, volume 6 of Atlantis Studies in Computing. Atlantis, 2015. URL: https://doi.org/10.2991/978-94-6239-097-3.
  45. Benno Schwikowski and Ewald Speckenmeyer. On enumerating all minimal solutions of feedback problems. Discrete Applied Mathematics, 117(1-3):253-265, 2002. URL: https://doi.org/10.1016/S0166-218X(00)00339-5.
  46. Yann Strozecki. Enumeration complexity and matroid decomposition. PhD thesis, Université Paris Diderot - Paris 7, Paris, France, 2010. Google Scholar
  47. Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28-42, 2006. URL: https://doi.org/10.1016/j.tcs.2006.06.015.
  48. Kunihiro Wasa. Enumeration of enumeration algorithms. arXiv:1605.05102, 2016. Google Scholar
  49. E. S. Wolk. The comparability graph of a tree. Proceedings of the American Mathematical Society, 13:789-795, 1962. URL: https://doi.org/10.1090/S0002-9939-1962-0172273-0.
  50. Jing-Ho Yan, Jer-Jeong Chen, and Gerard Jennhwa Chang. Quasi-threshold graphs. Discrete Applied Mathematics, 69(3):247-255, 1996. URL: https://doi.org/10.1016/0166-218X(96)00094-7.
  51. Jie You, Jianxin Wang, and Yixin Cao. Approximate association via dissociation. Discrete Applied Mathematics, 219:202-209, 2017. URL: https://doi.org/10.1016/j.dam.2016.11.007.
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