• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
https://arxiv.org/abs/1711.00667v2
Date
2018
Conference title
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)
Conference date
2018-01
Conference city
New Orleans, Louisiana
Conference country
United States
Book title
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)
Book author
Czumaj, Artur
Publisher
Society for Industrial and Applied Mathematics
ISBN
978-1-61197-503-1
Number of pages
2764
Pages
1665-1684
Publication identifier
10.1137/1.9781611975031.109
Metadata
Show full item record
Author(s)
Kim, Eun Jung
Laboratoire 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
Graphs

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity of Grundy Coloring and Its Variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
  • Thumbnail
    Complexity of Grundy coloring and its variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
  • Thumbnail
    Subexponential and FPT-time Inapproximability of Independent Set and Related Problems 
    Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2012) Document de travail / Working paper
  • Thumbnail
    The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation 
    Kim, Eun Jung; Ordyniak, Sebastian; Szeider, Stefan (2014) Communication / Conférence
  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo