Document Open Access Logo

Erdös-Pósa Property of Obstructions to Interval Graphs

Authors Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.7.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Akanksha Agrawal
Daniel Lokshtanov
Pranabendu Misra
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Erdös-Pósa Property of Obstructions to Interval Graphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.7

Abstract

The duality between packing and covering problems lies at the heart of fundamental combinatorial proofs, as well as well-known algorithmic methods such as the primal-dual method for approximation and win/win-approach for parameterized analysis. The very essence of this duality is encompassed by a well-known property called the Erdös-Pósa property, which has been extensively studied for over five decades. Informally, we say that a class of graphs F admits the Erdös-Pósa property if there exists f such that for any graph G, either G has  vertex-disjoint "copies" of the graphs in F, or there is a set S \subseteq V(G) of f(k) vertices that intersects all copies of the graphs in F. In the context of any graph class G, the most natural question that arises in this regard is as follows - do obstructions to G have the Erdös-Pósa property? Having this view in mind, we focus on the class of interval graphs. Structural properties of interval graphs are intensively studied, also as they lead to the design of polynomial-time algorithms for classic problems that are NP-hard on general graphs.  Nevertheless, about one of the most basic properties of such graphs, namely, the Erdös-Pósa property, nothing is known. In this paper, we settle this anomaly: we prove that the family of obstructions to interval graphs - namely, the family of chordless cycles and ATs---admits the Erdös-Pósa property. Our main theorem immediately results in an algorithm to decide whether an input graph G has vertex-disjoint ATs and chordless cycles, or there exists a set of O(k^2 log k) vertices in G that hits all ATs and chordless cycles.

Subject Classification

Keywords
  • Interval Graphs
  • Obstructions
  • Erdös-Pósa Property

Metrics

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

References

  1. Noga Alon. Covering a hypergraph of subgraphs. Discrete Mathematics, 257(2-3):249-254, 2002. Google Scholar
  2. Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. The erdos-posa property for directed graphs. CoRR, abs/1603.02504, 2016. URL: http://arxiv.org/abs/1603.02504.
  3. Julio Aracena, Jacques Demongeot, and Eric Goles. Positive and negative circuits in discrete neural networks. IEEE Transactions on Neural Networks, 15(1):77-83, 2004. Google Scholar
  4. Etienne Birmelé, J Adrian Bondy, and Bruce A Reed. The Erdős-Pósa property for long circuits. Combinatorica, 27(2):135-145, 2007. Google Scholar
  5. John Adrian Bondy, Uppaluri Siva Ramachandra Murty, et al. Graph theory with applications, volume 290. Citeseer, 1976. Google Scholar
  6. Nicolas Bousquet. Hitting sets: VC-dimension and Multicut. PhD thesis, Université Montpellier II-Sciences et Techniques du Languedoc, 2013. Google Scholar
  7. Nicolas Bousquet and Stéphan Thomassé. Vc-dimension and Erdős-Pósa property. Discrete Mathematics, 338(12):2302-2317, 2015. Google Scholar
  8. Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad. Graph classes: a survey. SIAM, 1999. Google Scholar
  9. Henning Bruhn, Felix Joos, and Oliver Schaudt. Long cycles through prescribed vertices have the Erdős-Pósa property. Journal of Graph Theory, 2017. Google Scholar
  10. Yixin Cao. Linear recognition of almost interval graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1096-1115. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch77.
  11. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3):21:1-21:35, 2015. URL: http://dx.doi.org/10.1145/2629595.
  12. Chandra Chekuri and Julia Chuzhoy. Large-treewidth graph decompositions and applications. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 291-300, 2013. Google Scholar
  13. Reinhard Diestel. Graph Theory. Springer-Verlag, Heidelberg, 4th edition, 2010. Google Scholar
  14. P Erdős and L Pósa. On independent circuits contained in a graph. Canad. J. Math., 17:347–352, 1965. Google Scholar
  15. Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta. Approximate min-max relations for odd cycles in planar graphs. Mathematical programming, 110(1):71-91, 2007. Google Scholar
  16. Jim Geelen and Kasper Kabell. The Erdős-Pósa property for matroid circuits. Journal of Combinatorial Theory, Series B, 99(2):407-419, 2009. Google Scholar
  17. Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Packing and covering immersion-expansions of planar sub-cubic graphs. Eur. J. Comb., 65:154-167, 2017. URL: http://dx.doi.org/10.1016/j.ejc.2017.05.009.
  18. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. Google Scholar
  19. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science &Business Media, 2012. Google Scholar
  20. Bertrand Guenin and Robin Thomas. Packing directed circuits exactly. Combinatorica, 31(4):397-421, 2011. Google Scholar
  21. András Gyárfás and Jenö Lehel. A helly-type problem in trees. In Colloquia mathematica Societatis Jànos Bolyai, volume 4, pages 571-584, 1970. Google Scholar
  22. Frédéric Havet and Ana Karolinna Maia. On disjoint directed cycles with prescribed minimum lengths. Research Report RR-8286, INRIA, 2013. Google Scholar
  23. Winfried Hochstättler, Robert Nickel, and Britta Peis. Two disjoint negative cycles in a signed graph. Electronic Notes in Discrete Mathematics, 25:107-111, 2006. Google Scholar
  24. Felix Joos. Parity linkage and the erdős-pósa property of odd cycles through prescribed vertices in highly connected graphs. Journal of Graph Theory, 85(4):747-758, 2017. URL: http://dx.doi.org/10.1002/jgt.22103.
  25. O joung Kwon and Eun Jung Kim. Erdős-Pósa property of chordless cycles and its application. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, To Appear, 2018. Google Scholar
  26. Naonori Kakimura and Ken-ichi Kawarabayashi. Fixed-parameter tractability for subset feedback set problems with parity constraints. Theoretical Computer Science, 576:61-76, 2015. Google Scholar
  27. Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. Packing cycles through prescribed vertices. Journal of Combinatorial Theory, Series B, 101(5):378-381, 2011. Google Scholar
  28. Ken-ichi Kawarabayashi and Bruce Reed. Highly parity linked graphs. Combinatorica, 29(2):215-225, 2009. Google Scholar
  29. Ken-ichi Kawarabayashi and Paul Wollan. Non-zero disjoint cycles in highly connected group labelled graphs. Journal of Combinatorial Theory, Series B, 96(2):296-301, 2006. Google Scholar
  30. Dénes König. Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77(4):453-465, 1916. Google Scholar
  31. Chun-Hung Liu. Packing and covering immersions in 4-edge-connected graphs. CoRR, abs/1505.00867, 2015. URL: https://arxiv.org/abs/1505.00867.
  32. Claudio L Lucchesi and DH Younger. A minimax theorem for directed graphs. Journal of the London Mathematical Society, 2(3):369-374, 1978. Google Scholar
  33. Karl Menger. Zur allgemeinen kurventheorie. Fund. Math., 10(4):96–115, 1927. Google Scholar
  34. Frank Mousset, Andreas Noever, Nemanja Škorić, and Felix Weissenberger. A tight Erdős-Pósa function for long cycles. Journal of Combinatorial Theory, Series B, 125:21-32, 2017. Google Scholar
  35. Matteo Pontecorvi and Paul Wollan. Disjoint cycles intersecting a set of vertices. Journal of Combinatorial Theory, Series B, 102(5):1134-1141, 2012. Google Scholar
  36. Dieter Rautenbach and Bruce Reed. The Erdős-Pósa property for odd cycles in highly connected graphs. Combinatorica, 21(2):267-278, 2001. Google Scholar
  37. Jean-Florent Raymond and Dimitrios M Thilikos. Recent techniques and results on the Erdős-Pósa property. Discrete Applied Mathematics, 2017. Google Scholar
  38. Bruce Reed. Tree Width and Tangles: A New Connectivity Measure and Some Applications, page 87–162. Cambridge University Press, 1997. Google Scholar
  39. Bruce Reed. Mangoes and blueberries. Combinatorica, 19(2):267-296, 1999. Google Scholar
  40. Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  41. Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph. J. Comb. Theory, Ser. B, 62(2):323-348, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1073.
  42. Neil Robertson and P.D Seymour. Graph minors. v. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. Google Scholar
  43. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science &Business Media, 2002. Google Scholar
  44. Paul D. Seymour. Packing circuits in eulerian digraphs. Combinatorica, 16(2):223-231, 1996. Google Scholar
  45. Miklós Simonovits. A new proof and generalizations of a theorem of Erdős-Pósa on graphs without k+ 1 independent circuits. Acta Mathematica Hungarica, 18(1-2):191-206, 1967. Google Scholar
  46. Mechthild Stoer. Design of survivable networks. Springer, 2006. Google Scholar
  47. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, 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: http://dx.doi.org/10.1007/978-3-540-70575-8_52.
  48. Carsten Thomassen. The Erdős-Pósa property for odd cycles in graphs of large connectivity. Combinatorica, 21(2):321-333, 2001. 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