Speaker: Christophe Paul,
LIRMM, Universite de Montpellier
Topic: A linear vertex kernel for the feedback arc set problem in tournaments and some applications of modular decomposition in fixed parameter algorithms.
Abstract: The existence of a fixed
parameterized (FPT) algorithm for a parameterized problem is known to be
equivalent to the existence of a kernelization algorithm: a polytime algorithm
that reduces the parameterized instance to an equivalent instance whose size is
bounded by a function of the parameter only. The question for a FPT
problem is whether or not it admits a polynomial (in the parameter) size
kernel. After a brief introduction to kernelization techniques, the talk
contains two parts:
Feedback Arc Set in Tournaments.
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
talk, we present 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
\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.
decomposition and polynomial size kernels.
of the reduction rules of our kernelization algorithm deals with the existence
of a large (with respect to k) transitive module in a non reduced
instance. In the last few years, a few kernelization results have been
obtained for parameterized graph modification problems such as cluster
editing. We give a brief overview of these known polynomial kernels.
For Additional Information, Contact: