Treewidth Workshop 2011

• Marek Cygan (Warsaw University, Poland), Cut&count technique for connectivity problems
• Fabian Hundertmark ( Universität Hamburg, Germany),  Canonical tree-decompositions and nested separation systems 
• Daniel Lokshtanov (UCSD, USA), Running Time Lower Bounds for Algorithms on Graphs of Bounded Treewidth
• Dániel Marx (Humboldt University, Germany), Finding Topological Subgraphs is Fixed-Parameter Tractable
• Peter Rossmanith (RWTH Aachen, Germany), A Game-Theoretic Approach to Courcelle's Theorem
• Saket Saurabh  (IMS, Chennai, India), Approximation  via Treewidth

There is no participation fee, and the workshop includes free coffee breaks and lunches for registered participants. For accommodation you have to contact a hotel yourself. To register for the workshop send a letter containing the following information before April 15 to Yngve VIllanger yngve.villanger*at*ii.uib.no

NAME:

DEPARTMENT, UNIVERSITY, COUNTRY:

and indicate whether you are interested in giving a talk. For PhD students, also please organize a brief letter of reference from advisor.

The following moderate price hotels are nearby the workshop site

• Steens Hotel
• Hotel Park
• Terminus Hotel

• From airport to Bergen center. Take bus "Flybussen" to the city center (Central bus station). The bus costs 95 NOK single, 150 NOK return. Taxi will be between 300 and 400 NOK.   
• From Bergen center. The workshop will be at VilVite center (10 minutes walk from the central bus station) If you have been visited us before, this is 50 meters from the Institute of Informatics. Here is how to get there and here is Google map. 

• Saket Saurabh        (Institute of Mathematical Sciences, Chennai, India)
• Peter Rossmanith    (RWTH Aachen University, Germany)
• Daniel Marx        (Humboldt University, Germany)
• Marek Cygan        (University of Warsaw, Poland)
• Daniel Lokshtanov    (UCSD, USA)
• Pål Grønås Drange    (University of Bergen, Norway)
• Pinar Heggernes        (University of Bergen, Norway)
• Erik Jan van Leeuwen    (University of Bergen, Norway)
• Jan Arne Telle        (University of Bergen, Norway)
• Frederic Dorn        (University of Bergen, Norway)
• Martin Vatshelle    (University of Bergen, Norway)
• Pim van 't Hof        (University of Bergen, Norway)
• Dieter Kratsch        (Universite de Metz, France)
• Haiko Muller        (University of Leeds, UK)   
• Marcin Pilipczuk    (University of Warsaw, Poland)
• Fabian Hundertmark    (Universitat Hamburg, Germany)   
• Archontia Giannopoulou    (National and Kapodistrian University of Athens, Greece)
• Daniel Paulusma     (University of Durham, UK)
• Serge Gaspers         (Vienna University of Technology, Austria)
• Petr Golovach        (University of Durham, UK)
• Alexander Langer    (RWTH Aachen University, Germany)
• Marcin Kaminski        (Universite Libre de Bruxelles, Belgium)
• Dietmar Berwanger    (LSV, CNRS and ENS Cachan, France)
• Michał Pilipczuk (University of Warsaw, Poland)
• Reza Saei        (University of Bergen, Norway)
• Sigve Hortemo Sæther   (University of Bergen, Norway)
• Rémy Belmonte (University of Bergen, Norway)
• Yuri Rabinovich (University of Haifa, Israel)
• Fedor Fomin (University of Bergen, Norway)
• Yngve Villanger (University of Bergen, Norway)     
• Sadia Sharmin (University of Bergen, Norway)
• Erik Parmann    (University of Bergen, Norway)

May 19, Thursday

• 09.00-09.10 Opening
• 09.10-10.10 Daniel Marx, Finding Topological Subgraphs is Fixed-Parameter Tractable
• 10.10-10.40 Haiko Muller, Stable degree
• 10.40 - 11.10 Coffee break
• 11.10 - 12.10 Peter Rossmanith, A Game-Theoretic Approach to Courcelle's Theorem
• 12.10 - 14. 00 Lunch
• 14.00 - 15.00 Fabian Hundertmark, Canonical tree-decompositions and nested separation systems
• 15.00 - 15.30 Coffee break
• 15.30 - 16. 30 Daniel Lokshtanov, Running Time Lower Bounds for Algorithms on Graphs of Bounded Treewidth
• 19.00 Dinner at Zupperia (Nordahl Bruns gate 9)

May 20, Friday

• 09.10-10.10 Marek Cygan, Cut&count technique for connectivity problems
• 10.10-10.40 Michal Pilipczuk, Problems parameterized by treewidth tractable in single exponential time: a logical approach  
• 10.40 - 11.10 Coffee break
• 11.10 - 12.10 Saket Saurabh, Approximation  via Treewidth
• 12.10 - 14. 00 Lunch
• 14.00 - 15.00  Yngve Villanger, Four steps and a Subexponential Parameterized Algorithm for Minimum Fill-in
• 15.00 - 15.30 Coffee break
• Concluding remarks, discussions

Saket Saurabh

Title:  Approximation  via Treewidth

Abstract: One of the well known methods for designing PTAS and EPTAS on planar graphs is Baker's Layering technique. A modern interpretation of this is that we decompose a planar graph into several graphs of bounded treewidth and then obtain solution on each part in polynomial time and then combine them to get an EPTAS. We will show another utility of treewidth in approximation algorithm. This method works for general graphs rather than graphs with structural properties. Using this we get a generic approximation algorithm with factor O(\sqrt{n}) for deleting vertices to get into a fixed minor closed family F.
(This is based on joint work with F. Fomin, D. Lokshtanov, N. Misra and G. Philip and  appears in STACS 2011).

 Peter Rossmanith 

Title: A Game-Theoretic Approach to Courcelle's Theorem

Abstract: Courcelle's Theorem states that all MSO-definable problems
can be solved in linear time on graphs of bounded treewidth.
The standard approach of constructing a tree automaton from
the MSO-formula and running this automaton on the tree
decomposition often fails because the automaton cannot be
constructed.  We implemented a program that does not use
tree automata, but constructs game trees for each node of
the tree decomposition.  From these game trees optimal
solutions can easily be computed.  Several algorithmic
improvements were necessary to turn this idea into practically
useful software. Joint work with Alexander Langer.

Fabian Hundertmark

Title: Canonical tree-decompositions and nested separation systems.

Abstract: here

Daniel Marx

Title: Finding Topological Subgraphs is Fixed-Parameter Tractable

Abstract: We show that for every fixed undirected graph H, there is an O(|V(G)|³) time algorithm that tests, given a graph G, if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)|³)  time algorithm that tests if there is an immersion of H into a given graph G. This answers another open question raised by Downey and Fellows in 1992.
 

Yngve Villanger

Title: Four steps and a Subexponential Parameterized Algorithm for Minimum Fill-in

Abstract:  The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable  in time O(2^O(k) +k^2 nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. In the talk we will discuss four different techniques, i.e. kernelization, branching, extracting potential parts of a solution, and dynamic programming over combinatorial objects.
In combination this give the first subexponential parameterized algorithm solving  Minimum Fill-in in time O(2^O(\sqrt{k} log k) +k^2 nm).  This  substantially lower the complexity of the problem. ETH based lower bounds and other related problems where the same technique applies will also be discussed.

Marek Cygan

Title: Cut&count technique for connectivity problems

Abstract: For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time.

We breach this gap by introducing a technique we named Cut&Count that
allows to produce c^tw V^O(1) Monte Carlo algorithms for most
connectivity-type problems, including Hamiltonian Path, Feedback
Vertex Set and Connected Dominating Set, consequently answering the
question raised by Lokshtanov, Marx and Saurabh in a surprising way.
The constant c we obtain is in all cases small (at most 4 for
undirected problems and at most 6 for directed ones). Our results have
consequences in various fields, like FPT algorithms, exact and
approximate algorithms on planar and H-minor-free graphs and
algorithms on graphs of bounded degree. In particular we show 3^k and
2^k parameterized Monte Carlo algorithms for Feedback Vertex Set and
Connected Vertex Cover problems respectively, when parameterized by
the solution size.

The results are based on joint work with Jesper Nederlof, Marcin
Pilipczuk, Michal Pilipczuk, Johan M.M. van Rooij and Jakub Onufry
Wojtaszczyk.

Daniel Lokshtanov

Title:  Running Time Lower Bounds for Algorithms on Graphs of Bounded Treewidth

Abstract:  We survey some of the recent running time lower bounds for algorithms on graphs of bounded treewidth. We consider three different lower bounds; 

(1) A f(tw)n^o(tw) lower bound for Capacitated Dominating Set under ETH,

(2) a 2^{O(tw log tw)} lower bound for Chromatic Number,

(3) a (3-e)^tw lower bound for Dominating Set under the Strong ETH.

The considered lower bounds match the running times of the best known algorithms for these problems.

• Fedor Fomin
• Yngve Villanger