CISPA
Browse
cispa_all_3303.pdf (552.82 kB)

Chordless Cycle Packing Is Fixed-Parameter Tractable

Download (552.82 kB)
conference contribution
posted on 2023-11-29, 18:14 authored by Dániel MarxDániel Marx
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.

History

Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

European Symposium on Algorithms (ESA)

Legacy Posted Date

2020-12-03

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3303, title = "Chordless Cycle Packing Is Fixed-Parameter Tractable", author = "Marx, Dániel", booktitle="{European Symposium on Algorithms (ESA)}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC