DOS Opt Seminar

Event Details
  • Date/Time:
    • Wednesday November 7, 2012
      11:00 am - 12:00 pm
  • Location: ISyE Executive Classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Opt Seminar

Full Summary: No summary paragraph submitted.

TITLE: Complexity results of some partial cut and covering problems

SPEAKER: Pierre Le Bodic


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 29, 2012 - 3:18am
  • Last Updated: Oct 7, 2016 - 10:00pm