Erdős-Pósa property of chordless cycles and its applications
Kim, Eun Jung; Kwon, O-joung (2018), Erdős-Pósa property of chordless cycles and its applications, in Czumaj, Artur, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18), Society for Industrial and Applied Mathematics, p. 1665-1684. 10.1137/1.9781611975031.109
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/1711.00667v2Date
2018Conference title
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)Conference date
2018-01Conference city
New Orleans, LouisianaConference country
United StatesBook title
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)Book author
Czumaj, ArturPublisher
Society for Industrial and Applied Mathematics
ISBN
978-1-61197-503-1
Number of pages
2764Pages
1665-1684
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kwon, O-joung
autre
Abstract (EN)
A chordless cycle in a graph G is an induced subgraph of G which is a cycle of length at least four. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k + 1 vertex-disjoint chordless cycles, or ck2 log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O(opt log opt) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ ≥ 5 do not have the Erdős-Pósa property.As a corollary, for a non-negative integral function w defined on the vertex set of a graph G, the minimum value Σx∊S w(x) over all vertex sets S hitting all cycles of G is at most O(k2 log k) where k is the maximum number of cycles (not necessarily vertex-disjoint) in G such that each vertex υ is used at most w(υ) times.Subjects / Keywords
GraphsRelated items
Showing items related by title and author.
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
-
Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2012) Document de travail / Working paper
-
Kim, Eun Jung; Ordyniak, Sebastian; Szeider, Stefan (2014) Communication / Conférence
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié