← 研踪 PaperTrailarXiv:2611.15024 · v1
$k$-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms
首次提交 2026-11-11 12:37
版本更新 2026-11-11 12:37
雷达观测 2026-11-13 10:09
摘要
Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms. However, for the \textsc{Feedback Vertex Set} problem, this approach faces a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by any function of the solution size~. To overcome this limitation, we introduce a data structure called a \emph{-product list}, which implicitly encodes all minimal solutions while admitting non-minimal ones to maintain efficiency. We present FPT algorithms for computing such lists not only for the \textsc{Feedback Vertex Set} problem but also for its natural generalizations, the \textsc{-Forest Deletion Set} problem and the \textsc{-Pseudoforest Deletion Set} problem. Our framework yields simple FPT algorithms for a wide range of variants, providing the first such results in several cases and demonstrating the broad applicability of our approach.
作者备注：38 pages, Full version of the IPEC 2026 paper
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 12:37 · 最新观测版本
$k$-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms
Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms. However, for the \textsc{Feedback Vertex Set} problem, this approach faces a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by any function of the solution size~. To overcome this limitation, we introduce a data structure called a \emph{-product list}, which implicitly encodes all minimal solutions while admitting non-minimal ones to maintain efficiency. We present FPT algorithms for computing such lists not only for the \textsc{Feedback Vertex Set} problem but also for its natural generalizations, the \textsc{-Forest Deletion Set} problem and the \textsc{-Pseudoforest Deletion Set} problem. Our framework yields simple FPT algorithms for a wide range of variants, providing the first such results in several cases and demonstrating the broad applicability of our approach.
查看此版本解读 →查看此版本原文 ↗