Show simple item record

dc.contributor.authorKim, Eun Jung
dc.contributor.authorKwon, O-joung
dc.date.accessioned2019-06-25T10:22:45Z
dc.date.available2019-06-25T10:22:45Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19024
dc.language.isoenen
dc.subjectGraphsen
dc.subject.ddc511en
dc.titleErdős-Pósa property of chordless cycles and its applicationsen
dc.typeCommunication / Conférence
dc.description.abstractenA 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.en
dc.identifier.citationpages1665-1684en
dc.relation.ispartoftitleProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)en
dc.relation.ispartofeditorCzumaj, Artur
dc.relation.ispartofpublnameSociety for Industrial and Applied Mathematicsen
dc.relation.ispartofdate169-02
dc.relation.ispartofpages2764en
dc.relation.ispartofurl10.1137/1.9781611975031en
dc.identifier.urlsitehttps://arxiv.org/abs/1711.00667v2en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-1-61197-503-1en
dc.relation.conftitle29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 18)en
dc.relation.confdate2018-01
dc.relation.confcityNew Orleans, Louisianaen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.identifier.doi10.1137/1.9781611975031.109en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-31T15:24:00Z
hal.person.labIds989
hal.person.labIds153012
hal.identifierhal-02164728*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record