Send email Copy Email Address

Chordless Cycle Packing Is Fixed-Parameter Tractable


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.

Conference / Medium

ESA 2020

Date published


Date last modified

2021-05-03 12:14:13