# W[2]

**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.