Kernels for feedback arc set in tournaments (Q657916): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Created claim: Wikidata QID (P12): Q60488571, #quickstatements; #temporary_batch_1711234560214 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q60488571 / rank | |||
Normal rank |
Revision as of 01:07, 24 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Kernels for feedback arc set in tournaments |
scientific article |
Statements
Kernels for feedback arc set in tournaments (English)
0 references
11 January 2012
0 references
From the 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^{{\prime}}\) on \(O(k)\) vertices. In fact, given any fixed \(\epsilon >0\), the kernelized instance has at most \((2+\epsilon)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.''
0 references
feedback arc set
0 references
tournaments
0 references
directed graph
0 references
digraph
0 references
kernelization
0 references
parameterized algorithms
0 references
graph algorithms
0 references