Document Open Access Logo

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

Authors Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.57.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Archontia C. Giannopoulou
Michal Pilipczuk
Jean-Florent Raymond
Dimitrios M. Thilikos
Marcin Wrochna

Cite As Get BibTex

Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.57

Abstract

Suppose F is a finite family of graphs. We consider the following meta-problem, called F-Immersion Deletion: given a graph G and an integer k, decide whether the deletion of at most k edges of G can result in a graph that does not contain any graph from F as an immersion. This problem is a close relative of the F-Minor Deletion problem studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to remove all minor models of graphs from F.
We prove that whenever all graphs from F are connected  and at least one graph of F is planar and subcubic, then the F-Immersion Deletion problem admits:
- a constant-factor approximation algorithm running in time O(m^3  n^3 log m)
- a linear kernel that can be computed in time O(m^4 n^3 log m) and
- a O(2^{O(k)} + m^4 n^3 log m)-time fixed-parameter algorithm,
where n,m count the vertices and edges of the input graph. Our findings mirror those of Fomin et al. [FOCS 2012], who obtained similar results for F-Minor Deletion, under the assumption that at least one graph from F is planar.
An important difference is that we are able to obtain a linear kernel for F-Immersion Deletion, while the exponent of the kernel of Fomin et al. depends heavily on the family F. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This reveals that the kernelization complexity of F-Immersion Deletion is quite different than that of F-Minor Deletion.

Subject Classification

Keywords
  • Kernelization
  • Approximation
  • Immersion
  • Protrusion
  • Tree-cut width

Metrics

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

References

  1. Rémy Belmonte, Archontia Giannopoulou, Daniel Lokshtanov, and Dimitrios M. Thilikos. The Structure of W₄-Immersion-Free Graphs. ArXiv e-prints 1602.02002, February 2016. Google Scholar
  2. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  3. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, November 2016. URL: http://dx.doi.org/10.1145/2973749.
  4. Heather D. Booth, Rajeev Govindan, Michael A. Langston, and Siddharthan Ramachandramurthi. Fast algorithms for K_4 immersion testing. J. Algorithms, 30(2):344-378, 1999. Google Scholar
  5. Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos. An O(log OPT)-approximation for covering/packing minor models of θ_r. Algorithmica, 2017. To appear. Google Scholar
  6. Rajesh Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Marcin Pilipczuk, and Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput., 45(4):1171-1229, 2016. Google Scholar
  7. Bruno Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  9. Matt Devos, Zdeněk Dvořák, Jacob Fox, Jessica McDonald, Bojan Mohar, and Diego Scheide. A minimum degree condition forcing complete graph immersion. Combinatorica, 34(3):279-298, 2014. Google Scholar
  10. Zdeněk Dvořák and Paul Wollan. A structure theorem for strong immersions. J. Graph Theory, 83(2):152-163, 2016. URL: http://dx.doi.org/10.1002/jgt.21990.
  11. Zdeněk Dvořák and Liana Yepremyan. Complete graph immersions and minimum degree. ArXiv e-prints 1512.00513, December 2015. Google Scholar
  12. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  13. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-Deletion: Approximation and optimal FPT algorithms. ArXiv e-prints 1204.4230, October 2012. Google Scholar
  14. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of FOCS 2012, pages 470-479. IEEE Computer Society, 2012. Google Scholar
  15. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of SODA 2010, pages 503-510. SIAM, 2010. Google Scholar
  16. Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Proceedings of MFCS 2015, volume 9235 of Lecture Notes in Computer Science, pages 348-360. Springer, 2015. Google Scholar
  17. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Trans. Algorithms, 13(3):35:1-35:35, March 2017. URL: http://dx.doi.org/10.1145/3029051.
  18. Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Packing and covering immersion models of planar subcubic graphs. In Proceedings of WG 2016, pages 74-84. Springer, 2016. Preprint: ArXiv e-prints 1602.04042. Google Scholar
  19. Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, Jean-Florent Raymond, and Marcin Wrochna. Linear kernels for edge deletion problems to immersion-closed graph classes. ArXiv e-prints 1609.07780, September 2016. URL: https://arxiv.org/abs/1609.07780.
  20. Archontia C. Giannopoulou, Iosif Salem, and Dimitris Zoros. Effective computation of immersion obstructions for unions of graph classes. J. Comput. Syst. Sci., 80(1):207-216, 2014. Google Scholar
  21. Rajeev Govindan and Siddharthan Ramachandramurthi. A weak immersion relation on graphs and its applications. Disc. Math., 230(1–3):189-206, 2001. Google Scholar
  22. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of STOC 2011, pages 479-488. ACM, 2011. Google Scholar
  23. Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan. On an edge ranking problem of trees and graphs. Discrete Appl. Math., 30(1):43-52, 1991. Google Scholar
  24. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In Proceedings of ICALP 2013, volume 7965 of Lecture Notes in Computer Science, pages 613-624. Springer, 2013. Google Scholar
  25. Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-approximation for tree-cut decomposition. Algorithmica, pages 1-20, 2016. URL: http://dx.doi.org/10.1007/s00453-016-0245-5.
  26. Tak Wah Lam and Fung Ling Yue. Edge ranking of graphs is hard. Discrete Appl. Math., 85(1):71-86, 1998. Google Scholar
  27. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
  28. Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. SIAM J. Discrete Math., 28(1):503-520, 2014. Google Scholar
  29. Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  30. N. Robertson and P.D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. Google Scholar
  31. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. Google Scholar
  32. Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B, 92(2):325-357, 2004. Google Scholar
  33. Neil Robertson and Paul D. Seymour. Graph minors. XXIII. Nash-Williams' immersion conjecture. J. Comb. Theory, Ser. B, 100(2):181-205, 2010. Google Scholar
  34. Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217-241, 1994. Google Scholar
  35. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms, 56(1):1-24, 2005. Google Scholar
  36. Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47-66, 2015. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact