Graph Parameters: Structural Properties and Algorithmic Applications

Abstract

Parameterized complexity provides a rich toolbox for dealing with intractable problems that arise in different areas of computer science. One of the main aims here is to obtain a more fine-grained complexity analysis of computationally hard problems based not only on the input size but also on some parameter. The analogues of polynomially solvable problems here are fixed-parameter tractable problems, which admit an algorithm with running time f(k) · n^O(1) for some computable function f, where n is an input size and k is a parameter. In this work, we investigate the parameterized complexity of problems whose instances admit graph representations, so the parameters we consider are tied to structural properties of the input graph. We focus on decompositional graph parameters, which allow to decompose graphs into components along some tree-like structure.Among the decompositional graph parameters, the most prominent is treewidth, which measures the treelikeness of a graph in terms of vertex separators. To handle problems where it does not help to achieve fixed-parameter tractability, more restrictive vertex-cut based parameters such as pathwidth, treedepth, or vertex cover number are commonly used. However, for some problems, it is natural to consider edge-cut-based parameters instead, and here the choice is much more limited, leaving large gaps in the understanding of complexity of these problems. Our aim in this work is to fill this gap in the hierarchy of edge-cut based graph parameters. As our main contribution, we introduce a new parameter slim tree-cut width which is a restriction of tree-cut width, and show that it is a perfect fit for a number of classical graph problems where the parameterization by the latter does not help.We perform a deep theoretical study of the structural properties of slim tree-cut width. In particular, we provide three equivalent characterizations of the parameter: (i) actual slim tree-cut width, defined with the help of tree-cut decompositions and inheriting many advantages of the tree-cut width, (ii) super edge-cut width, providing an easy-to-use in algorithms decomposition in terms of a spanning tree, and (iii) the characterization in terms of block decompositions, allowing to decompose graph into components of small treewidth and maximum degree. We provide multiple examples witnessing that slim tree-cut width and other edge-cut based parameters help achieve tractability not only in many classical graph problems but also in some fundamental problems originating from AI, such as data completion and causal network learning.