- Title: “Tree Decompositions and Routing Problems”
- When: November 12, 2014 — 10:00
- Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
- Pascal Berthomé (Referee), LIFO, Univ. Orléans & INSA Centre-Val de Loire, France
- Nicolas Hanusse (Referee), CNRS, Bordeaux University, France
- David Coudert (co-supervisor), COATI, Inria/I3S-UNS, France
- Hao Li, LRI, CNRS, France
- Jérôme Galtier, Orange Labs, France
- Nicolas Nisse (co-supervisor), COATI, Inria/I3S-UNS, France
- Igor Litovsky, I3S, Univ. Nice Sophia Antipolis, France
Abstract: A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts.
In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k ≥ 4, we prove it is NP-hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014.
In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-time algorithm that either returns an induced cycle of length at least k + 1 of a graph G or compute a k-good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica.
In the second part of the thesis, we focus on routing problems. In Chapter 4, we design a compact routing scheme that achieves good performance in the class of graphs admitting k-good tree decompositions.
In Chapter 5, we consider the prize collecting Steiner tree problem (a generalization of the Steiner-tree problem with weighted nodes and edges). We design two risk models of the problem when the weights are given as intervals. In these models, we design polynomial-time algorithms for graphs with small treewidth. These results have been published in AAIM 2010 and the journal Acta Mathematicae Applicatae Sinica.
Finally, in Chapter 6, we consider the gathering problem in grids and in presence of interferences. We design approximation algorithms (up to small additive constants depending on the interferences) for solving this problem. This work is in revision for TCS.
Keywords: Tree Decomposition, Compact Routing Scheme, Prize Collecting Steiner Tree, Gathering.