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.
- XNLP. A class first defined by Elberfeld et al at IPEC 2012. We have shown that many problems `with a linear structure' are complete for the class, including classics like Bandwidth, Scheduling Jobs with Predecessor Constraints,
but also problems with the pathwidth, linear cliquewidth, or linear mim-width as parameter.
- Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. With Carla Groenland, Jesper Nederlof, Celine Swennenhuis. FOCS 2022.
- XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure. With Carla Groenland, Hugo Jacob, Lars Jaffke, Paloma Lima. IPEC 2022, Best Paper.
- Problems hard for treewidth but easy for stable gonality. With Gunter Cornelissen and Marieke van der Wegen, WG 2022. Amongst others, several variants of flow and
graph orientation problems are shown to be complete for XNLP with pathwidth as parameter.
- XALP. A class introduced in the paper On the Complexity of Problems on Tree-structured Graphs. Well known problems with treewidth or cliquewidth as parameter can
be shown to be complete for this class, and some problems to find tree-structured representations of graphs.
- On the Complexity of Problems on Tree-structured Graphs. With Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk. IPEC 2022. Introduces XALP, with euivalent
definitions, and a first set of complete problems.
- On the parameterized complexity of computing tree-partitions. With Carla Groenland, Hugo Jacob. IPEC 2022. Shows approximation for tree partition width, and gives
complete problems for XALP.
Related are the recent papers:
Note: links to papers go to the arXiv-versions, which are not necessarily the last versions.