A Polynomial Kernel for Funnel Arc Deletion Set
| Autor: | Garlet Milani, Marcelo |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
funnels General Computer Science parameterized algorithm Applied Mathematics 510 Mathematik kernels Computer Science Applications Theory of computation → Fixed parameter tractability Computer Science - Data Structures and Algorithms directed feedback arc set graph editing Data Structures and Algorithms (cs.DS) ddc:510 |
| Zdroj: | Algorithmica. 84:2358-2378 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-022-00960-w |
| Popis: | In Directed Feeback Arc Set (DFAS) we search for a set of at most $k$ arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider $\mathcal{C}$-Arc Deletion Set ($\mathcal{C}$-ADS), a variant of DFAS where we want to remove at most $k$ arcs from the input digraph in order to turn it into a digraph of a class $\mathcal{C}$. In this work, we choose $\mathcal{C}$ to be the class of funnels. Funnel-Arc Deletion Set is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to $k$. So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-Arc Deletion Set with $\mathcal{O}(k^6)$ many vertices and $\mathcal{O}(k^7)$ many arcs, computable in $\mathcal{O}(nm)$ time, where $n$ is the number of vertices and $m$ the number of arcs in the input digraph. Accepted at IPEC 2020 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink