文章基本信息

标题：Chordless Cycle Packing Is Fixed-Parameter Tractable
本地全文：下载
作者：D{'a}niel Marx
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：71:1-71:19
DOI：10.4230/LIPIcs.ESA.2020.71
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：chordal graphs; packing; fixed-parameter tractability