University of Leicester


Computer Science Internal Seminars

The Internal Seminar Series is a relaxed forum for members of the Department to present their current research and discuss ideas of interest. Invited speakers are also welcome, in particular for presentations that might be too specialised for a general computer science audience as on the Friday's seminar.

Semester 2

Room this semester is BEN LT3.

Seminar programme

Seminar details

Secure message transmison on directed graphs (Slides)

Ludovic Renou (Leicester, Department of Economics)
Thu 24 Feb, 10:00 in BEN LT3 (Host: Alexander Kurz)

Semester 1

Room this semester is ENG LT1.

Seminar programme

Seminar details

Parameterization of graph separation problems: current results and further challenges

Igor Razgon ()
Thu 9 Dec, 10:00 in ENG LT1 (Host: )

Fixed-parameter computation is a methodology of coping with NP-hardness that, under certain conditions, allows to solve hard optimization problems both precisely and efficiency. According to this methodology, a problem is associated with a parameter $k$ and solved by an exponential time algorithm whose exponential part solely depends on the parameter while dependnency on the input size $n$ is uniformly polynomial, i.e. the degree of the polynomial is a constant, usually not greater than 3. When the parameter is small, we get a low-polynomial algorithm solving an NP-hard problem to optimality. Problems that can be solved in this way are called fixed-parameter tractable (FPT). The parameter choice depends on the particular application and can be, for example, maximum or minimum allowed size of the output or some structural measure of the input, e.g. treewidth.

This talk is related to parameterization of graph separation problems where the task is to find the smallest set of vertices separating some predefined pairs of terminals, possibly under additional constraints. In the first part of this talk, I will informally define a fixed-parameter algorithm and describe two fixed-parameter algorithms for the Vertex Cover problem. In the second part of the talk I will describe an algorithm for solving the multiway cut problem and show how the main idea of this algorithm has helped to show the fixed-parameter tractability of such challenging graph separation problems as Directed Feedback Vertex Set, minimum 2CNF deletion, and Multicut. In the final part of the talk I will outline the current challenges related to the parameterization of graph separation problems. The main challenge is kernelization of these problems, i.e. designing a polynomial-time procedure that squeezes the initial instance of the problem so that its size polynomially depends on the parameter. Such procedure being applied at the preprocessing stage can significantly enhance any algorithm solving the given problem and hence understanding kernelizability of parameterized problems is a research direction of a great practical importance.

The talk is self-contained and assumes no prior familiarity with the area.

Author: Alexander Kurz (kurz mcs le ac uk), T: 0116 252 5356.
© University of Leicester . Last modified: 9th February 2012, 21:28:52
Informatics Web Maintainer. This document has been approved by the Head of Department.