 |
HAL-LIRMM - Open Archive |  |
Conference papers
Kernels for Feedback Arc Set In Tournaments
Abstract : A tournament T = (V , A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T ′ on O(k) vertices. In fact, given any fixed ϵ > 0, the kernelized instance has at most (2 + ϵ)k vertices. Our result improves the previous known bound of O(k2 ) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k- FAST.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432668
Contributor : Christophe Paul <>
Submitted on : Wednesday, June 30, 2021 - 12:35:57 PM
Last modification on : Wednesday, June 30, 2021 - 1:25:32 PM
Contributor : Christophe Paul <>
Submitted on : Wednesday, June 30, 2021 - 12:35:57 PM
Last modification on : Wednesday, June 30, 2021 - 1:25:32 PM
File
09005.BessyStephane.2305.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License