Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical Aspects

April 7-11, 2008

CIRM, Luminy, Marseille (France)

Organized by the French ANR project "Décomposition de graphes et algorithmes"

Invited speakers:
  • Bodlaender Hans (Univ. Utrecht): Algorithms to find tree decompositions: theory and practice
In this talk, a survey will be given on algorithms that determine the treewidth of a given graph, and find tree decompositions of graphs. In this survey, theoretical results will be discussed, like the recent exact algorithms, results using potential maximal cliques, and approximation algorithms, but also experimental work will be discussed: algorithms and their implementation for computing the treewidth exactly, or giving heuristic upper- or lower-bounds, and for preprocessing the graph with safe rules. In many cases, there is an interesting interaction between theory and experiment.
  • Fellows Michael (Univ. of Newcastle): What about trees ? Description and analysis of complexity - some observations and horizons.

    One of the key themes in graph decompositions is the representation of graph classes in terms of: (a vertex-colored binary tree + an interpretation of the colors as graph-descriptive grammatical operators), as juxtaposed with the analysis of the computational complexity of the determination of properties of graphs in such classes as expressibility in forms of logic.  There are two countervailing flows / dramas of logic in this general situation.  We report some fresh observations and results about this situation and describe a wide-ranging program of open problems.
  • Fomin Fedor (Univ. Bergen): Parameterized algorithms for partial covering problems
The set covering problem, which is one of the  fundamental and classical problems in optimization, computer  science and complexity theory, is to cover a set of elements with the minimum number of sets. The variations of covering problems include well known problems like Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with minimum number of sets.

In this talk  we describe how to obtain parameterized algorithms for partial covering problems in graphs of bounded local treewidth and graphs excluding a fixed graph $H$ as a minor.
  • Kratsch Dieter (Univ. Metz): Fast Exponential-Time Algorithms to solve NP-complete problems exactly

    Some important part of the current research on the design and analysis of algorithms can be seen as trying to find better and better approaches for solving NP-complete problems. In most cases the notion of "solving a problem exactly" is relaxed: approximation algorithms, heuristics, randomized algorithms, parameterized algorithms, algorithms for restricted inputs, etc.

    One of the oldest methods dating back to the early sixties are exponential-time algorithms. This is the approach that tries to cope with NP-completeness in the strongest sense. The fundamental techniques to design and analyze fast exponential-time algorithms are branching algorithms and dynamic programming. Those two techniques and some less known ones will be presented and discussed with examples for the two classical NP-complete INDEPENDENT SET and COLORING. 
  • Makowsky Janos (Technion - Haifa): Connection matrices of numeric graph invariants

    Freedman, Lovasz and Schrijver (2007) introduced the connection matrix of a numeric graph invariant and used it to characterize those invariants which arise as weighted partition functions. Weighted partition functions are special cases of evaluations of MSOL-definable graph polynomials.

    In this talk we shall survey recent results of Lovasz and Szegedy and apply them to the study the connection matrices of evaluations of MSOL-definable graph polynomials.
  • Oum Sang-Il (KAIST, Korea): Finding branch-decompositions and rank-decompositions (Joint work with Petr Hlineny)

    We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most k if such exists. This algorithm works also for partitioned matroids. Both these algorithms are fixed-parameter tractable, that is, they run in time O(n^3) where n is the number of vertices / elements of the input, for each constant value of k and any fixed finite field. The previous best algorithm for construction of a branch-decomposition or a rank-decomposition of optimal width due to Oum and Seymour [Testing branch-width. J. Combin. Theory Ser. B, 97(3) (2007) 385–393] is not fixed-parameter tractable.
  • Thilikos Dimitrios (Univ. of Athens): Bidimensionality, decompositions and subexponential parameterized algorithms
We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. By subexponential parameterized algorithm we mean an algorithm that for a given input of length O(n) and parameter k, outputs solution the parameterized problem in  2^{O(\sqrt{k})} n^{O(1)} steps.

The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating  the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2^{O(\sqrt{k})} n^{O(1)} time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.