Document Open Access Logo

Polynomial Kernel for Immersion Hitting in Tournaments

Authors Łukasz Bożyk , Michał Pilipczuk

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2022.26.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • kernelization
  • graph immersion
  • tournament
  • protrusion

Metrics

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

Abstract

For a fixed simple digraph H without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain H as an immersion. We prove that for every H, this problem admits a polynomial kernel when parameterized by the number of deleted arcs. The degree of the bound on the kernel size depends on H.

Cite As Get BibTex

Łukasz Bożyk and Michał Pilipczuk. Polynomial Kernel for Immersion Hitting in Tournaments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.26

Author Details

Łukasz Bożyk
  • University of Warsaw, Poland
Michał Pilipczuk
  • University of Warsaw, Poland

Funding

This work is a part of projects that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreements No. 714704 (Ł. Bożyk) and No. 948057 (Mi. Pilipczuk).

References

  1. Noga Alon, Daniel Lokshtanov, and Saket Saurabh. Fast FAST. In 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, volume 5555 of Lecture Notes in Computer Science, pages 49-58. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_6.
  2. Florian Barbero, Christophe Paul, and Michał Pilipczuk. Exploring the complexity of layout parameters in tournaments and semicomplete digraphs. ACM Trans. Algorithms, 14(3):38:1-38:31, 2018. URL: https://doi.org/10.1145/3196276.
  3. Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi. Packing arc-disjoint cycles in tournaments. Algorithmica, 83(5):1393-1420, 2021. URL: https://doi.org/10.1007/s00453-020-00788-2.
  4. Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, 77(6):1071-1078, 2011. URL: https://doi.org/10.1016/j.jcss.2010.10.001.
  5. 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, 2016. URL: https://doi.org/10.1145/2973749.
  6. Mikolaj Bojanczyk. Factorization forests. In 13th International Conference on Developments in Language Theory, DLT 2009, volume 5583 of Lecture Notes in Computer Science, pages 1-17. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02737-6_1.
  7. Marthe Bonamy and Michał Pilipczuk. Graphs of bounded cliquewidth are polynomially χ-bounded. Advances in Combinatorics, 2020:8, 2020. Google Scholar
  8. Łukasz Bożyk and Michał Pilipczuk. On the Erdős-Pósa property for immersions and topological minors in tournaments. Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, April 2022. URL: https://doi.org/10.46298/dmtcs.7099.
  9. Maria Chudnovsky, Alexandra Ovetsky Fradkin, and Paul D. Seymour. Tournament immersion and cutwidth. Journal of Combinatorial Theory, Series B, 102(1):93-101, 2012. URL: https://doi.org/10.1016/j.jctb.2011.05.001.
  10. Maria Chudnovsky and Paul D. Seymour. A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B, 101(1):47-53, 2011. URL: https://doi.org/10.1016/j.jctb.2010.10.003.
  11. Uriel Feige. Faster FAST (Feedback Arc Set in Tournaments). CoRR, abs/0911.5094, 2009. URL: http://arxiv.org/abs/0911.5094.
  12. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-Deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 470-479. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  13. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  14. Fedor V. Fomin and Michał Pilipczuk. On width measures and topological problems on semi-complete digraphs. Journal of Combinatorial Theory, Series B, 138:78-165, 2019. URL: https://doi.org/10.1016/j.jctb.2019.01.006.
  15. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Transactions on Algorithms, 13(3):35:1-35:35, 2017. URL: https://doi.org/10.1145/3029051.
  16. Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon. The directed flat wall theorem. In 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 239-258. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.15.
  17. Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon. Directed tangle tree-decompositions and applications. In 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 377-405. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.19.
  18. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear kernels for edge deletion problems to immersion-closed graph classes. SIAM Journal on Discrete Mathematics, 35(1):105-151, 2021. URL: https://doi.org/10.1137/18M1228839.
  19. Marek Karpinski and Warren Schudy. Faster algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. In 21st International Symposium on Algorithms and Computation, ISAAC 2010, volume 6506 of Lecture Notes in Computer Science, pages 3-14. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17517-6_3.
  20. Ken-ichi Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 655-664. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746586.
  21. Ilhee Kim and Paul D. Seymour. Tournament minors. Journal of Combinatorial Theory, Series B, 112:138-153, 2015. URL: https://doi.org/10.1016/j.jctb.2014.12.005.
  22. Manfred Kufleitner. The height of factorization forests. In 33rd International Symposium Mathematical Foundations of Computer Science 2008, MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 443-454. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_36.
  23. Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2014-2033. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.120.
  24. Jaroslav Nešetřil, Roman Rabinovich, Patrice Ossona de Mendez, and Sebastian Siebertz. Linear rankwidth meets stability. In 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1180-1199. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.72.
  25. Alexandra Ovetsky Fradkin. Forbidden structures and algorithms in graphs and digraphs. PhD thesis, Princeton University, 2011. Google Scholar
  26. Alexandra Ovetsky Fradkin and Paul D. Seymour. Tournament pathwidth and topological containment. Journal of Combinatorial Theory, Series B, 103(3):374-384, 2013. URL: https://doi.org/10.1016/j.jctb.2013.03.001.
  27. Alexandra Ovetsky Fradkin and Paul D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. Journal of Combinatorial Theory, Series B, 110:19-46, 2015. URL: https://doi.org/10.1016/j.jctb.2014.07.002.
  28. Jean-Florent Raymond. Hitting minors, subdivisions, and immersions in tournaments. Discrete Mathematics and Theoretical Computer Science, 20(1), 2018. URL: http://dmtcs.episciences.org/4212.
  29. Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65-94, 1990. URL: https://doi.org/10.1016/0304-3975(90)90047-L.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »