Document Open Access Logo

Lean Tree-Cut Decompositions: Obstructions and Algorithms

Authors Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond , Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.32.pdf
  • Filesize: 0.63 MB
  • 14 pages

Document Identifiers

Author Details

Archontia C. Giannopoulou
  • LaS team, Technische Universität Berlin, Germany
O-joung Kwon
  • Department of Mathematics, Incheon National University, South Korea
Jean-Florent Raymond
  • LaS team, Technische Universität Berlin, Germany
Dimitrios M. Thilikos
  • AlGCo project-team, LIRMM, Université de Montpellier, CNRS, Montpellier, France

Funding

  • Giannopoulou, Archontia C.: Supported by the ERC consolidator grant Distruct-648527.
  • Kwon, O-joung: Supported by the ERC consolidator grant Distruct-648527 and by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294).
  • Raymond, Jean-Florent: Supported by ERC consolidator grant Distruct-648527.
  • Thilikos, Dimitrios M.: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

Acknowledgements

We are grateful to Michał Pilipczuk and Marcin Wrochna for extensive discussions about the proof of Theorem 1.

Cite As Get BibTex

Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.32

Abstract

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47 - 66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1):67 - 76, 1990]. This allows us to give, for every k in N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Fixed parameter tractability
Keywords
  • tree-cut width
  • lean decompositions
  • immersions
  • obstructions
  • parameterized algorithms

Metrics

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

Related Versions

References

  1. Jeffrey Azzato. Linked tree-decompositions of represented infinite matroids. Journal of Combinatorial Theory, Series B, 101(3):123-140, 2011. URL: http://dx.doi.org/10.1016/j.jctb.2010.12.003.
  2. Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability and Computing, 11(6):541-547, 2002. Google Scholar
  3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A (c^kn) 5-Approximation Algorithm for Treewidth. SIAM Journal of Computing, 45(2):317-378, 2016. Google Scholar
  4. Hans L Bodlaender, Fedor V Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M Thilikos. (Meta) kernelization. Journal of the ACM, 63(5):44, 2016. Google Scholar
  5. Heather Booth, Rajeev Govindan, Michael A. Langston, and Siddharthan Ramachandramurthi. Cutwidth approximation in linear time. In Proceedings of the Second Great Lakes Symposium on VLSI, pages 70-73. IEEE, 1992. Google Scholar
  6. Johannes Carmesin, Reinhard Diestel, M. Hamann, and Fabian Hundertmark. k-Blocks: A Connectivity Invariant for Graphs. SIAM Journal on Discrete Mathematics, 28(4):1876-1891, 2014. Google Scholar
  7. Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos. An O(log OPT)-approximation for covering and packing minor models of θ_r. Algorithmica, April 2017. URL: http://dx.doi.org/10.1007/s00453-017-0313-5.
  8. Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M Thilikos. Minors in graphs of large θ_r-girth. European Journal of Combinatorics, 65:106-121, 2017. Google Scholar
  9. Joshua Erde. A unified treatment of linked and lean tree-decompositions. Journal of Combinatorial Theory, Series B, 130:114-143, 2018. Google Scholar
  10. 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
  11. Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. In Mathematical foundations of computer science 2015. Part II, volume 9235 of Lecture Notes in Computer Science, pages 348-360. Springer, Heidelberg, 2015. Google Scholar
  12. James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. Journal of Combinatorial Theory, Series B, 84(2):270-290, 2002. Google Scholar
  13. Jim Geelen and Benson Joeris. A generalization of the Grid Theorem. arXiv preprint, 2016. URL: http://arxiv.org/abs/1609.09098.
  14. Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean tree-cut decompositions: obstructions and algorithms. arXiv e-prints, August 2018. URL: http://arxiv.org/abs/1808.00863.
  15. 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, July 10-14, 2017, Warsaw, Poland, pages 57:1-57:15, 2017. Google Scholar
  16. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. Algorithmica, March 2018. URL: http://dx.doi.org/10.1007/s00453-018-0424-7.
  17. Rajeev Govindan and Siddharthan Ramachandramurthi. A weak immersion relation on graphs and its applications. Discrete Mathematics, 230(1–3):189-206, 2001. Google Scholar
  18. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding Topological Subgraphs is Fixed-parameter Tractable. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 479-488, New York, NY, USA, 2011. ACM. Google Scholar
  19. Tibor Grünwald. Ein Neuer Beweis Eines Mengerschen Satzes. Journal of the London Mathematical Society, s1-13(3):188-192, 1938. URL: http://dx.doi.org/10.1112/jlms/s1-13.3.188.
  20. Mamadou Moustapha Kanté and O-joung Kwon. An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width. CoRR, abs/1412.6201, 2014. URL: http://arxiv.org/abs/1412.6201.
  21. Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. Algorithmica, 80(1):116-135, 2018. Google Scholar
  22. Ilhee Kim and Paul D. Seymour. Tournament minors. Journal of Combinatorial Theory, Series B, 112:138-153, 2015. Google Scholar
  23. Shiva Kintali. Directed Minors III. Directed Linked Decompositions. CoRR, 2014. URL: http://arxiv.org/abs/1404.5976.
  24. Jens Lagergren. Upper Bounds on the Size of Obstructions and Intertwines. Journal of Combinatorial Theory, Series B, 73(1):7-40, 1998. Google Scholar
  25. Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 1(10):96-115, 1927. Google Scholar
  26. Sang-il Oum. Rank-width and vertex-minors. Journal of Combinatorial Theory, Series B, 95(1):79-100, 2005. Google Scholar
  27. Neil Robertson and Paul Seymour. Graph Minors. XXIII. Nash-Williams' Immersion Conjecture. Journal of Combinatorial Theory, Series B, 100(2):181-205, March 2010. Google Scholar
  28. Neil Robertson and Paul D. Seymour. Graph Minors. II. Algorithmic Aspects of Tree-Width. Journal of Algorithms, 7(3):309-322, 1986. Google Scholar
  29. Neil Robertson and Paul D. Seymour. Graph Minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(2):92-114, 1986. Google Scholar
  30. Neil Robertson and Paul D Seymour. Graph Minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. Google Scholar
  31. Robin Thomas. A menger-like property of tree-width: The finite case. Journal of Combinatorial Theory, Series B, 48(1):67-76, 1990. Google Scholar
  32. Paul Wollan. The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series 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