Archive for the ‘2012’ Category

Gary MacGillivray, Graph Partitions

Saturday, October 13th, 2012
Graph Partitions
Gary MacGillivray
Department of Mathematics and Statistics, University of Victoria, Victoria, B.C. Canada
2012/11/9 Fri 4PM-5PM
We consider partitions of the vertices of a graph into a fixed number of labelled cells such that (i) the subgraph induced by each cell belongs to a family that depends on the cell, and (ii) edges joining vertices in different cells are allowed only if the cells correspond to adjacent vertices in a given pattern graph H. Both polynomiality and NP-completeness results are presented. Tha focus is on methods that give polynomial time algorithms.
This is a joint work with Peter Dukes and Steve Lowdon.

(Colloquium) Jaroslav Nešetřil, Limits of Structures and Sparse-Dense Dichotomy

Saturday, September 29th, 2012

FYI (Department Colloquium)

Limits of Structures and Sparse-Dense Dichotomy
Jaroslav Nešetřil
Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague
2012/11/1 Thu 4:30PM-5:30PM (Room 1501, Bldg. E6)
Based on the newly understood dichotomy of sparse and dense structures, we provide the general framework for study of structural (mostly graph) limits. Our approach uses both model theoretic and analytic tools and uses structural theory of bounded expansion classes.

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

Sunday, September 16th, 2012
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 2O(k) n log2 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 2O(k)n2.
This is a joint work with Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar.

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

Saturday, September 15th, 2012
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 (s1,t1),…,(sk,tk), whether there is a collection of k pairwise vertex-disjoint paths linking si and ti, for i=1,…,k. In their f(k)n3 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)=2O(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 22o(k)nO(1) will probably require drastically different ideas from those in the irrelevant vertex technique.

Andreas Holmsen, On the Erdős-Szekeres Problem

Monday, September 10th, 2012
On the Erdős-Szekeres Problem
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2012/9/21 Fri 4PM-5PM
In 1935 Erdős and Szekeres showed that every “sufficiently large” set of points in general position in the plane contains a “large” subset which is in convex position. Since then many mathematicians have tried to determine good bounds for “sufficiently large” in  terms of “large”, as well as given numerous generalizations and refinements. In this talk I will survey this famous problem and extend it to a natural object which we call generalized wiring diagram. This unifies several proposed generalizations, and as a result we will settle several conjectures in this area. This is joint work with Michael Dobbins and Alfredo Hubard.