Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> JAN 29: Theory: Combinatorics CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
JAN 29: Theory: Combinatorics CS Seminar
Event date: Friday, January 29, 2010, at 2:00 PM
Location: Sandford Flemming Bldg. Rm SF3207
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:
1)
Parameterized Feedback Arc Set in Tournaments.
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 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.
2)
Modular decomposition and polynomial size kernels.
One 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: Derek Corneil