Seminars in October 2012

• Eun Jung Kim (김은정), Linear kernels and single-exponential algorithms via protrusion decompositions

  Linear kernels and single-exponential algorithms via protrusion decompositions

  Eun Jung Kim (김은정)
  CNRS, LAMSADE, Paris, France.

  2012/10/19 Fri 4PM-5PM

  A t-treewidth-modulator of a graph G is a set X⊆V(G) such that the treewidth of G-X is at most some constant t-1. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs G that come equipped with a t-treewidth-modulator. This decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results.
  We first show that any parameterized graph problem (with parameter k) that has finite integer index and is treewidth-bounding admits a linear kernel on H-topological-minor-free graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a t-treewidth-modulator of size O(k), for some constant t. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and H-minor-free graphs [Fomin et al., SODA 2010].
  Our second application concerns the Planar-F-Deletion problem. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, Planar-F-Deletion asks whether G has a set X⊆ V(G) such that |X|≤k and G-X is H-minor-free for every H∈F. Very recently, an algorithm for Planar-F-Deletion with running time 2^O(k) n log² n (such an algorithm is called single-exponential) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in F is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar-F-Deletion problem running in time 2^O(k)n².
  This is a joint work with Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar.

  Tags:

  • 김은정

• Philipp Klaus Krause, Irrelevant vertices for the planar Disjoint Paths Problem

  Irrelevant vertices for the planar Disjoint Paths Problem

  Philipp Klaus Krause
  Institut für Informatik, Goethe-Universität, Frankfurt am Main, Germany

  2012/10/11 Thu 4PM-5PM

  The Disjoint-Paths Problem asks, given a graph G and a set of pairs of terminals (s₁,t₁),…,(s_k,t_k), whether there is a collection of k pairwise vertex-disjoint paths linking s_i and t_i, for i=1,…,k. In their f(k)n³ algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g(k) there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose — very technical — proof gives a function g(k) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we prove this result for planar graphs achieving g(k)=2^O(k). Our bound is radically better than the bounds known for general graphs. Moreover, our proof is new and self-contained, and it strongly exploits the combinatorial properties of planar graphs. We also prove that our result is optimal, in the sense that the function g(k) cannot become better than exponential. Our results suggest that any algorithm for the Disjoint-Paths Problem that runs in time better than 2^2o(k)n^O(1) will probably require drastically different ideas from those in the irrelevant vertex technique.

  Tags:

  • PhilippKlausKrause