Chordless Cycle Packing Is Fixed-Parameter Tractable

Marx, Dániel
(2020) Chordless Cycle Packing Is Fixed-Parameter Tractable.
In: ESA 2020.
Conference: ESA European Symposium on Algorithms

LIPIcs-ESA-2020-71.pdf - Accepted Version

Download (566kB) | Preview


A chordless cycle or hole in a graph G is an induced cycle of length at least 4. In the Hole Packing problem, a graph G and an integer k is given, and the task is to find (if exists) a set of k pairwise vertex-disjoint chordless cycles. Our main result is showing that Hole Packing is fixed-parameter tractable (FPT), that is, can be solved in time f(k)n^O(1) for some function f depending only on k.


Actions (login required)

View Item View Item