Parameterized complexity

Research    -    Education    -    Group    -    Personal    -    Misc    -    Contact

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:

• 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.
  1. Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. With Carla Groenland, Jesper Nederlof, Celine Swennenhuis. FOCS 2022.
  2. XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure. With Carla Groenland, Hugo Jacob, Lars Jaffke, Paloma Lima. IPEC 2022, Best Paper.
  3. 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.
  1. 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.
  2. 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:

• Parameterized Complexities of Dominating and Independent Set Reconfiguration. With Carla Groenland and Celine Swennenhuis. IPEC 2021. We consider reconfiguration of dominating and independent sets, with the set size as parameter. Depending whether the number of moves is a parameter, given in unary, given in binary, or not specified, the problem is complete for W[1] (IS) respectively W[2] (DS), XNLP, XNL, or XL.
• Parameterized Complexity Results for Bayesian Inference. With Nils Donselaar and Johan Kwisthout. PGM 2022. The paper looks at a counting version of XNLP, and applies this to the inference problem from Probabilistic (or Bayesian) networks.
• List Colouring Trees in Logarithmic Space. With Carla Groenland and Hugo Jacob. The paper shows that the List Colouring problem for trees is in the class L (logarithmic space).
• The Parameterized Complexity Binary CSP for Graphs with a Small Vertex Cover and Related Results. The paper shows that the Binary CSP problem (Constraint Satisfaction Problems with constraints on pairs of variables, with multiple possible values per variable) is complete for the class W[3] when the size of a vertex cover is taken as parameter. The result is somewhat curious, in the sense that there are very few natural problems known to be complete for W[3]. Also, some related results.