Aims & Scope

The aim of this workshop is to promote the study of real-life motivated problems which includes appropriate choices of parameters, design and analysis of FPT algorithms, and development of kernelization techniques. We believe that the workshop will be of interest to a wide audience including the ICALP community and become the first in a series of APAC workshops.


It is well known that the vast majority of practical problems are NP-hard and thus we cannot hope to obtain algorithms which compute the exact solution efficiently. One way to overcome this obstacle is to settle for approximate solutions. However, is this really necessary? After all, the data of real-life problems are the outputs of other processes, such as natural selection, chemical and physical processes, and other algorithms. Whilst these data are often very large and complex, some structure is almost always present.

Parameterized complexity is an approach which uses the underlying structure of data to design efficient and exact algorithms. First, it uses a parameter to "capture" the amount of structure present in data —generally, the lower the parameter, the more structured it is. Here the meaning of "structured" depends on the choice of parameter. For instance, the well-known treewidth parameter measures how much a graph resembles a tree.

Once a suitable parameter is chosen, we can use it to develop efficient parameterized algorithms. The runtime of such parameterized algorithms depends both on the size of the input and the parameter. Ideally, a practical parameterized algorithm should run in time O(f(par) ·poly(n)), where poly(n) is a polynomial in the input size and f(par) is a computable function in the parameter (algorithms with a runtime of this form are called FPT, or fixed-parameter tractable). These algorithms can solve NP-hard problems on large instances efficiently (in polynomial or even linear time) as long as the value of the parameter is relatively small.

It is well known that the input of every FPT problem can be compressed, in polynomial time, such that its size will be bounded by a function of the parameter (in many cases, a polynomial). This compression (called kernelization in Parameterized Complexity community) amounts to a preprocessing with a worst case guarantee. Note that kernelization is of interest even if non-parameterized algorithms such as heuristics are used to solve the compressed instances of the problem.


The workshop program will consist of several invited talks. Everyone is most welcome to attend. The workshop fee is 35 British pounds which covers two coffee breaks, lunch and a coach to/from Leamington Spa for dinner.



The workshop is organized by Gregory Z. Gutin, Royal Holloway, University of London, UK


The workshop will take place in lecture room MS.03 in the building of the Warwick Mathematics Institute (Zeeman Building).

View Larger Map


8:50 Foreword (Gregory Z. Gutin)
9:009:45    Michael A. Langston
Uncovering Latent Relationships in High Dimensional Data with High Performance Parameterized Algorithms: A Smorgasbord of Applications
9:4510:30    Liming Cai
Parameterized Computation for Biomolecule Folding
10:3011:00 Coffee
11:0011:45 Norbert Zeh
Comparing Phylogenies: Kernelization, Depth-Bounded Search and Beyond
11:4512:30 Faisal Abu-Khzam
The Capacitated Cluster Edit Problem: Theory and Experiments
12:3014:00 Lunch and Discussion
14:0014:45 Rolf Niedermeier
Partitioning into Colorful Components: From Parameterized Algorithmics to Algorithm Engineering
14:4515:30 Stefan Szeider
Parameterized Complexity Results for Probabilistic Network Structure Learning
15:3016:00 Coffee
16:0016:45 Anders Yeo
Parameterized Complexity of Certain Information Security Problems
16:4517:30 Jiong Guo
Parameterized Complexity of Local Search Problems
17:30  Conclusion


Gregory Z. Gutin Michael A. Langston Liming Cai Norbert Zeh Faisal Abu-Khzam Rolf Niedermeier Stefan Szeider Anders Yeo Jiong Guo Hurry - session starts listening to announcements

Photos by Juraj Stacho.