|
Workshop
on Graph Decomposition: Theoretical, Algorithmic and
Logical
Aspects
April
7-11, 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 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.
|