A Complexity Dichotomy for the Steiner Multicut Problem

VCLA will host a talk by Matthias Mnich on January 8th, 2014.

ABSTRACT

Given an undirected graph G, a collection T = {T_1,...,T_t} of (not necessarily disjoint) vertex subsets of G, and an integer k, the Steiner Multicut problem asks if there is a set S of at most k edges or vertices such that the removal of S from G disconnects every set T_i, that is, at least one pair of vertices from each set T_i is disconnected in G S. This problem generalizes several well-studied graph cut problems, such as the Multicut problem where each set T_i has size two.

We provide a complete parameterized complexity dichotomy of the Steiner Multicut problem, for the parameters solutions k, maximum size of the T_i's, number of T_i's, and treewidth of G, for all versions with edge deletions and node deletions with and without deletable terminals. Most notably, we generalize the fixed-parameter algorithms for Edge Multicut by Marx and Razgon STOC 2011] and Bousquet et al. [STOC 2011] for parameter k to solve Edge Steiner Multicut for arbitrary sets T_i in time depending exponentially only on k and t.

(joint work with Karl Bringmann, Danny Hermelin and Erik Jan van Leeuwen)