Name
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 ( k 2 ) 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcss.2010.10.001 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
parameterized algorithms,input instance,equivalent instance,integer parameter k,kernelized instance,k vertex,acyclic digraph,graph algorithms,feedback arc set,feedback arc,k arc,feedback arc set problem,polynomial time,tournaments,k-feedback arc set,kernelization,discrete mathematics,polynomial time approximation scheme,directed graph,data structure | Journal | abs/0907.2165 |
Issue | ISSN | Citations |
6 | Journal of Computer and System Sciences | 21 |
PageRank | References | Authors |
0.79 | 20 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Fedor V. Fomin | 2 | 3139 | 192.21 |
| Serge Gaspers | 3 | 28 | 1.70 |
| Christophe Paul | 4 | 147 | 9.72 |
| Anthony Perez | 5 | 67 | 7.24 |
| Saket Saurabh | 6 | 2023 | 179.50 |
| Stéphan Thomassé | 7 | 651 | 66.03 |