Talks and Tutorials

Invited talks:

Daniel Marx, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary

Title: Randomized techniques for parameterized algorithms [13/09/12, 09:00-10:00]

Abstract: Since the introduction of the Color Coding technique in 1994 by Alon, Yuster, and Zwick, randomization has been part of the toolkit for proving fixed-parameter tractability results.  It seems that randomization is very well suited to parameterized algorithms: if the task is to find a solution of size k and only those random choices need to be correct that are directly related to the solution, then typically we can bound the error probability by a function of k. The talk will overview through various concrete examples how randomization appears in fixed-parameter tractability results.  We argue that in many cases randomization appears in form of a reduction: it allows us to reduce the problem we are trying to solve to an easier and more structured problem.

 

Andreas Björklund, Lund University, Lund, Sweden [14/09/12, 13:30-14:30]

Title: The path taken for k-path

Abstract: We give a historical account of the parametrized results for the k-PATH problem: given a graph G and a positive integer k, is there a simple path in G of length k. Throughout the years several ingenious approaches have been used, steadily decreasing the run time bound. Moreover, the techniques used have often found lots of other applications. We will revisit some of the old results, as well as cover the state-of-the-art techniques based on algebraic sieves. We will also briefly talk about what is known about counting k-paths.

 

Tutorials:

Saket Saurabh, The Institute of Mathematical Sciences, Chennai, India

Title: Subexponential Time Parameterized Algorithms 12/09/2012 [13:30]

Abstract: It is not completely known for what problems and in what graph classes subexponential  parameterized algorithms exist. Until recently the only tool known to obtain  subexponential  parameterized algorithm was Bidimensioanlity.  The theory is based on algorithmic and  combinatorial extensions to various parts of Graph Minors Theory of Robertson and Seymour   and provides a simple criteria for checking whether a parameterized problem is solvable in  subexponential time on sparse graphs. Recently variations of color-coding has been  proposed to obtain  subexponential algorithm on dense graphs. There are also problems  (for an example parameterized Minimum Fill-In)  for which problem specific subexponential  algorithm have been obtained. In this talk we will survey the known techniques to obtain  subexponential time parameterized algorithms. We will also outline the challenges and  problems in this area.

 

Michał Pilipczuk, Univerist of Bergen, Bergen, Norway

Title: Lower bounds for polynomial kernelization 13/09/2012 [15:00]

Abstract:

Although construction of polynomial-time preprocessing routines accompanied the search for fixed-parameter tractable algorithms from the very beginning of parameterized complexity, it was not until 2008 that a framework for proving implausability of kernelization with polynomial size guarantees was established. The seminal work of Fortnow and Santhanam, adapted to the parameterized world by Bodlaender, Downey, Fellows and Hermelin, provided the technique of distillation, using which it is possible to prove that if a problem admits a certain composition property, then existence of a polynomial kernel for it would cause coNP\subseteq NP/poly and, consequently, collapse of the polynomial hierarchy. Since then, many fixed-parameter tractable problems have been proven not to admit polynomial kernels (under aforementioned complexity assumption), and investigating polynomial kernelizability became a second stage of analyzing a parameterized problem, after establishing its parameterized complexity.

During this tutorial we will introduce formally the composition framework, and illustrate it with a number of case-study examples from various subfields of parameterized complexity. We will also survey recent advances on establishing tight bounds on kernel sizes in terms of the degree of the polynomial, i.e., weak compositions, as well as attempts to prove lower bounds based on different complexity assumptions.

Additional information