Back to Search
Start Over
Erdős-Pósa property of chordless cycles and its applications.
- Source :
-
Journal of Combinatorial Theory - Series B . Nov2020, Vol. 145, p65-112. 48p. - Publication Year :
- 2020
-
Abstract
- A chordless cycle, or equivalently a hole, in a graph G is an induced subgraph of G which is a cycle of length at least 4. 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 c 1 k 2 log k + c 2 vertices hitting every chordless cycle for some constants c 1 and c 2. 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 145
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 146013505
- Full Text :
- https://doi.org/10.1016/j.jctb.2020.05.002