Workshop
on Graph Decomposition: Theoretical, Algorithmic and
Logical
Aspects
April
711, 2008
CIRM,
Luminy, Marseille (France)
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 lowerbounds, 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 vertexcolored binary tree + an interpretation of the colors as
graphdescriptive 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 wideranging 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 ExponentialTime Algorithms to solve NPcomplete 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 NPcomplete
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 exponentialtime algorithms. This
is the approach that tries to cope with NPcompleteness in the
strongest sense. The fundamental techniques to design and analyze fast
exponentialtime 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 NPcomplete
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 MSOLdefinable 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
MSOLdefinable graph polynomials.

Oum SangIl (KAIST, Korea): Finding branchdecompositions and rankdecompositions (Joint work with Petr Hlineny)
We present a new algorithm
that can output the rankdecomposition 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 ﬁxed ﬁnite ﬁeld, outputs its branchdecomposition of
width at most k if such exists. This algorithm works also for
partitioned matroids. Both these algorithms are ﬁxedparameter
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
ﬁxed ﬁnite ﬁeld. The previous best algorithm for construction of a
branchdecomposition or a rankdecomposition of optimal width due to
Oum and Seymour [Testing branchwidth. J. Combin. Theory Ser. B, 97(3)
(2007) 385–393] is not ﬁxedparameter 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 subexponential
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.
