Separators with Non-Hereditary Properties

We investigate the problem of finding small s–t separators that induce graphs having certain properties. It is known that finding a minimum clique s–t separator is polynomial-time solvable (Tarjan 1985), while for example the problems of finding a minimum s–t separator that is a connected graph or an independent set are fixed-parameter tractable (Marx, O’Sullivan and Razgon, manuscript). We explore how these results generalize, for instance, when we require that the separator has diameter at most d (the clique being the special case when d=1) or when the separator is required to be c-connected (the connected separators being the special case when c=1). In general, these problems turn out to be W[1]-hard, although it is curious that the problem of finding a 2-connected separator is FPT.

It also turns out that on graphs of bounded degree, the problem of finding a minimum s-t separator with any decidable property is FPT. After an overview of the results, we will discuss some specific algorithms.