Analysing flow-like problems parameterised by tree-depth

Abstract

In the field of parameterised complexity, there has been a significant amount of research into the parameters treewidth and pathwidth, but not a comparable amount of research into the related tree-depth parameter. In this paper, we try to expand our knowledge about the hardness of a set of ‘flow-like’ graph problems when parameterised by tree-depth, similar to work done in [1] and [2] where the same set of problems was considered for pathwidth and treewidth respectively. We also provide hardness proofs for the class XSLP, which was defined in [3] by Bodlaender et al., and is intended to serve as a ‘natural home’ for problems parameterised by tree-depth, similar to how XALP and XNLP are intended as ‘natural homes’ for problems parameterised by treewidth and foor pathwidth respectively. Furthermore, by showing that a parameterised reduction exists between any two problems in the set of flow-like problems we consider when using the tree-depth parameter, we support a conjecture that this set of problems is in a different complexity class that is distinct from XSLP.