Document Open Access Logo

Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration

Authors Petr A. Golovach , Christian Komusiewicz , Dieter Kratsch, Van Bang Le

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.37.pdf
  • Filesize: 0.82 MB
  • 18 pages

Document Identifiers

Author Details

Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Christian Komusiewicz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany
Dieter Kratsch
  • LGIMP, Université de Lorraine, Metz, France
Van Bang Le
  • Institut für Informatik, Universität Rostock, Germany

Funding

  • Golovach, Petr A.: Supported by the Research Council of Norway via the project "MULTIVAL" (grant no. 263317).

Acknowledgements

We dedicate this paper to the memory of our coauthor and friend Dieter Kratsch who recently passed away. Without Dieter, this paper would have never been written.

Cite AsGet BibTex

Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.37

Abstract

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • enumeration problems
  • polynomial delay
  • output-sensitive algorithms
  • kernelization
  • structural parameterizations
  • matching cuts

Metrics

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

Related Versions

References

  1. N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. On structural parameterizations of the matching cut problem. In Xiaofeng Gao, Hongwei Du, and Meng Han, editors, Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II, volume 10628 of Lecture Notes in Computer Science, pages 475-482, 2017. Google Scholar
  2. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. J. Comput. Syst. Sci., 103:61-77, 2019. URL: https://doi.org/10.1016/j.jcss.2019.02.004.
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: https://doi.org/10.1137/S0097539793251219.
  4. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  5. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discret. Math., 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  6. Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 16:1-16:19, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.16.
  7. Vasek Chvátal. Recognizing decomposable graphs. Journal of Graph Theory, 8(1):51-53, 1984. URL: https://doi.org/10.1002/jgt.3190080106.
  8. Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discret. Appl. Math., 157(12):2675-2700, 2009. URL: https://doi.org/10.1016/j.dam.2008.08.021.
  9. Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. Paradigms for parameterized enumeration. Theory Comput. Syst., 60(4):737-758, 2017. URL: https://doi.org/10.1007/s00224-016-9702-4.
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  11. Peter Damaschke. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci., 351(3):337-350, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.004.
  12. Peter Damaschke. Fixed-parameter enumerability of cluster editing and related problems. Theory Comput. Syst., 46(2):261-283, 2010. Google Scholar
  13. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  14. Henning Fernau. On parameterized enumeration. In Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings, volume 2387 of Lecture Notes in Computer Science, pages 564-573. Springer, 2002. URL: https://doi.org/10.1007/3-540-45655-4_60.
  15. Fedor V. Fomin, Daniel Lokshtanove, Saket Saurabh, and Meirav Zehavi. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge, 2019. URL: https://doi.org/10.1017/9781107415157.
  16. Fedor V. Fomin, Saket Saurabh, and Yngve Villanger. A polynomial kernel for proper interval vertex deletion. SIAM J. Discret. Math., 27(4):1964-1976, 2013. URL: https://doi.org/10.1137/12089051X.
  17. Robert Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In Dániel Marx and Peter Rossmanith, editors, Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, volume 7112 of Lecture Notes in Computer Science, pages 259-271. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-28050-4_21.
  18. Robert Ganian. Improving vertex cover as a graph parameter. Discret. Math. Theor. Comput. Sci., 17(2):77-100, 2015. URL: http://dmtcs.episciences.org/2136.
  19. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  20. Petr Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined notions of parameterized enumeration kernels with applications to matching cut enumerations. CoRR, abs2101.03800, 2021. URL: http://arxiv.org/abs/2101.03800.
  21. Guilherme C. M. Gomes and Ignasi Sau. Finding cuts of bounded degree: Complexity, FPT and exact algorithms, and kernelization. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 19:1-19:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.19.
  22. R. L. Graham. On primitive graphs and optimal vertex assignments. Ann. New York Acad. Sci., 175:170-186, 1970. Google Scholar
  23. Sun-Yuan Hsieh, Hoàng-Oanh Le, Van Bang Le, and Sheng-Lung Peng. Matching cut in graphs with large minimum degree. In Ding-Zhu Du, Zhenhua Duan, and Cong Tian, editors, Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings, volume 11653 of Lecture Notes in Computer Science, pages 301-312. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_25.
  24. George Karakostas. A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms, 5(4):41:1-41:8, 2009. URL: https://doi.org/10.1145/1597036.1597045.
  25. Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms. Discret. Appl. Math., 283:44-58, 2020. URL: https://doi.org/10.1016/j.dam.2019.12.010.
  26. Christian Komusiewicz and Johannes Uhlmann. A cubic-vertex kernel for flip consensus tree. Algorithmica, 68(1):81-108, 2014. Google Scholar
  27. Dieter Kratsch and Van Bang Le. Algorithms solving the matching cut problem. Theor. Comput. Sci., 609:328-335, 2016. URL: https://doi.org/10.1016/j.tcs.2015.10.016.
  28. Stefan Kratsch. Recent developments in kernelization: A survey. Bull. EATCS, 113, 2014. Google Scholar
  29. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  30. Andrea Marino. Analysis and enumeration, volume 6 of Atlantis Studies in Computing. Atlantis Press, Paris, 2015. Algorithms for biological graphs, With forewords by Tiziana Calamoneri and Pierluigi Crescenzi. Google Scholar
  31. Kitty Meeks. Randomised enumeration of small witnesses using a decision oracle. Algorithmica, 81(2):519-540, 2019. Google Scholar
  32. Arne Meier. Parametrised enumeration. Habilitation thesis, Leibniz Universität Hannover, 2020. URL: https://doi.org/10.15488/9427.
  33. Sang-il Oum. Approximating rank-width and clique-width quickly. ACM Trans. Algorithms, 5(1):10:1-10:20, 2008. URL: https://doi.org/10.1145/1435375.1435385.
  34. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/j.jctb.2005.10.006.
  35. Marko Samer and Stefan Szeider. Backdoor trees. In Dieter Fox and Carla P. Gomes, editors, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, pages 363-368. AAAI Press, 2008. URL: http://www.aaai.org/Library/AAAI/2008/aaai08-057.php.
  36. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 634-645. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_52.
  37. Kunihiro Wasa. Enumeration of enumeration algorithms. CoRR, abs/1605.05102, 2016. URL: http://arxiv.org/abs/1605.05102.
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