IPEC 2022

Parameterized complexity

Foto: Carla Groenland, Paloma Lima, Hans Bodlaender, Lars Jaffke, Hugo Jacob
Author of XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure; best paper IPEC 2022
Photo taken at IPEC (ALGO) 2022, Potsdam, Germany.

Research    -    Education    -    Group    -    Personal    -    Misc    -    Contact

A recent topic in my investigations is to look at the complexity structure of classes within XP. We look at parameterized problems: here, we identify a variable from the input called the parameter, which is considered to be relatively small. XP is the class of parameterized problems that can be solved in slicewise polynomial time: for each value of the parameter, we have a polynomial time algorithm. However, the exponent of this polynomial can grow with the parameter.

Inside the class XP, several subclasses of parameterized problems live. In addition to the classes, defined in research in the field in the 20th century, we can identify a number of other important classes. Interestingly, many natural and well studied problems known to be in XP but expected not to be fixed parameter tractable, appear to be complete for these classes. Such results pinpoint the computational complexity, and indicate the use of computational resources like memory (or tradeoff between space and memory) needed to solve the problems. Starring are:

Related are the recent papers:

Note: links to papers go to the arXiv-versions, which are not necessarily the last versions.