(2020) Chordless Cycle Packing Is Fixed-Parameter Tractable.
In: ESA 2020.
Conference:
ESA European Symposium on Algorithms
|
Text
LIPIcs-ESA-2020-71.pdf - Accepted Version Download (566kB) | Preview |
Abstract
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | ESA European Symposium on Algorithms |
| Depositing User: | Dániel Marx |
| Date Deposited: | 03 Dec 2020 10:32 |
| Last Modified: | 03 May 2021 12:14 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3303 |
Actions
Actions (login required)
 |
View Item |