Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Algorithmic Applications of Tree-Cut Width
Speaker:Eunjung Kim
coming from:CNRS / Universit├ę Paris Dauphine
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 18 November 2014
Duration:30 Minutes
Building:E1 4
Wollan has recently introduced the graph parameter tree-cut width, which plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not believed to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set and Imbalance parameterized by the tree-cut width of an input graph G. On the other hand, we show that List Coloring, Precoloring Extension and Boolean CSP (the latter parameterized by the tree-cut with of the incidence graph) are unlikely to be fixed parameter tractable when parameterized by tree-cut width. This is a joint work with Robert Ganian and Stefan Szeider.
Name(s):Holger Dell
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Holger Dell, 11/18/2014 11:39 AM
  • Holger Dell, 11/10/2014 05:08 PM
  • Holger Dell, 11/06/2014 09:41 PM
  • Holger Dell, 10/31/2014 02:22 PM
  • Holger Dell, 10/31/2014 02:21 PM -- Created document.