Home

Algorithms

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

 

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: 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)|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)|3time 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.