*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
