TITLE: Complexity results of some partial cut and covering problems

SPEAKER: Pierre Le Bodic

ABSTRACT:

In classical cut problems, the input consists of a graph and some set S to cut. Partial cut problems are a generalization of cut problems, in which, given an additional integer k, only a subset of S of cardinality at least k must be cut. The archetypal example is the partial multicut problem, in which S is a set of pairs of vertices. The focus of this article is on partial cut problems for which the classical version is easily solvable on some class of graphs. A variant of multiterminal cut is proven to become \NPhard{} when its partial version is considered. The major part of this talk is dedicated to designing a unified dynamic programming algorithm for partial cut problems. Using this result, many partial cut problems are proven to be FPT w.r.t. some parameters including the treewidth of the input graph, or, for the generalized version, pseudopolynomial if these parameters are fixed. A partial cover problem, namely partial dominating set, is also solved using this unified algorithm. Using these algorithms, FPTASs are then designed for generalized partial versions of multicut and multiterminal cut on bounded treewidth graphs. A (2+\epsilon)-approximation is also provided for the generalized partial multiterminal cut problem on general graphs, and adapted, with different ratios, to other variants.