# Treewidth Workshop 2011

Treewidth Workshop 2011

### Bergen, 19/05/2011 - 20/05/2011

The meeting will take place at VilVite center, in Bergen, starting on May 19 (Thursday) at 09.00. The workshop ends on May 20 (Friday) around 17.00. The format of the workshop will be several invited lectures on the recent advances in the area, short reports on new results, and slots for discussions and open problems.

Note that this workshop does not produce any proceedings and presentations here should not cause any problem for submitting the same material to a regular conference or journal.

## Invited speakers

**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*

## Registration

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.

## Accommodation

The following moderate price hotels are nearby the workshop site

## Arrival information

**From airport to Bergen center.***T*ake 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.

## Registered participants

- 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)

## Program

**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

## Abstracts

**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: C*anonical 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)| ^{3}) *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

^{3})*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.