Annual status workshop
TITLES AND ABSTRACTS 9 NOVEMBER:
Martin Skutella: Virtual Private Network Design and Tree Routings
Consider a communication network which is represented by an
undirected graph with edge costs. Within this network there is a set
of terminals which want to communicate with each other. However, the
exact amount of traffic between pairs of terminals is not known in
advance. Instead, each terminal has an upper bound on the cumulative
amount of traffic that it can send or receive. The task is to specify
a fixed communication path for any pair of terminals and to install
capacities on the edges of the graph at minimum cost supporting any
possible communication scenario. The complexity of this optimization
problem is open. It is however conjectured that there always exists
an optimal tree solution where the chosen communication paths form a
tree spanning all terminals. In this talk we give an introduction
into this problem and discuss recent results and developments. This
is based on joint work with Fabrizio Grandoni, Volker Kaibel, and
Marc Thurley: Partition Functions on Negative Weight Matrices
Partition functions are widely used in statistical physics to describe
important thermodynamical properties of particle systems. Being weighted
generalizations of graph-homomorphism counting problems, their computational
complexity has been studied exhaustively for the case of undirected graphs
and non-negative weights. Together with Leslie Ann Goldberg, Mark Jerrum and
Martin Grohe, I have worked on extending these results to negative weights. I
will talk about this work and related results.
Hiep Han: Weak regularity for hypergraphs
In the last decades Szemeredi's concept of regularity has proven to be
very successful in extremal combinatorics with many (algorithmic)
applications. Recently there were several attempts to generalize this
concept to hypergraphs resulting in different notions of quasi-random
In this talk we introduce some of these concepts and some open questions.
Daria Schymura: A probabilistic algorithm for approximating the maximal area
under translations and rigid motions
A probabilistic scheme for matching two shapes under translations, rigid
motions and similarities is presented. Shapes are modeled as bounded
polygonal regions in the plane. I show that in case of translations
and rigid motions an approximation of the maximal area of overlap is
Ronald Wotzlaw: Polytope Graphs, Skeleta, and Positive k-Spanning Sets of
TITLES AND ABSTRACTS 23 NOVEMBER:
Felix Breuer: Splitting Necklaces with Quotas
Consider a necklace of beads of n different colors. We are
faced with the task of cutting the necklace and distributing the pieces
among k thieves such that every thief gets the same number of beads of
each color. A famous theorem of Alon states that n*(k-1) cuts suffice.
What if one thief is supposed to get 1/3 and the other 2/3 of the beads
of each color? I conjecture that in this case the required number of
cuts is still independent of the total number of beads on the necklace.
This is an interesting conjecture, because the topological methods
employed in the proof of Alon's theorem do not seem to help in this case.
Subexponential Fixed-Parameter Tractability of Counting Problems
In the first phase of my PhD project, we intend to develop a theory of
subexponential fixed-parameter tractable counting problems. For
decision problems, such a theory is already known, and it is in a
beautiful way isomorphic to the theory of unbounded fixed-parameter
tractable problems. We hope to find a similar isomorphism for the
counting case. Apart from the theory, the project will also involve
the construction of subexponential -exact or approximate- counting
Jens Schmidt: Certifying graph algorithms
For some important problems on graphs exist very fast, but
complicated algorithms. E.g. testing a graph for planarity or for
3-connectivity has been solved with an optimal asymptotic running time
over 30 years ago. But up to now there are still contributions dealing
with those problems in order to make algorithms more understandable or
even correct some errors in them.
When implementing those complex algorithms it is essential to check if
the resulting program does what it should do. A possible way to
guarantee the correctness is to find a certificate for each solution,
that witnesses it and can be automatically checked. E.g. for the
planarity problem an embedding in the plane or a Kuratowski subdivision
would be such a certificate.
Paul Bonsma: An FPT Algorithm for Directed Spanning k-leaf
An out-branching of a directed graph is a rooted spanning tree with all
arcs directed outwards from the root. We consider the NP-complete problem
of deciding whether a given digraph on n vertices has an out-branching
with at least k leaves (Directed Spanning k-leaf). Loosely speaking, when
k is chosen as the parameter, an algorithm for this problem is said to be
fixed parameter tractable (FPT) when its running time is bounded by
g(n)f(k), where g(n) is a polynomial and f(k) may be an arbitrary function.
Recently FPT algorithms have been given for this problem, when
restricted to various graph classes such as strongly connected digraphs
and acyclic digraphs. We show how to extend these methods such that an
FPT algorithm is obtained for all digraphs.
This is based on joint work with Frederic Dorn.
About the Complexity of the (s,t)-Path Constrained Network Flow Problem
In the classical flow theory, flow is sent in a network from source
s to sink t respecting edge capacities. It is well known that
any flow can be decomposed in path flows and circle flows. In the
general case the set of paths used for the decomposition is not
In our case a set of (s,t)-paths P is given. We are
now interested in flows that send a least k units from s to
t and that can be decomposed using only the paths in P.
The so called (s,t)-Path constrained network flow problem is
This talk presents a short proof, that for the optimization problem,
i.e. sending as much flow as possible, there exists no approximation
algorithm with a factor better then n^e for some e>0, unless P=NP.
Mareike Massow: Linear Extensions of Finite Posets
Given a finite poset P, I am interested in the structure of the set of
linear extensions of P. We can define a graph G(P) on this set, the
linear extension graph of P, in which two linear extensions are adjacent
as vertices if they differ exactly by one adjacent transposition. I will
present recent results for the reconstruction problem: Given a graph G
which is known to be a linear extension graph, can we reconstruct the
Kolja Knauer: Upper Locally Distributive Lattices
Upper Locally Distributive Lattices (ULDs) are a
frequently appearing class of partial orders on combinatorial objects.
We give some examples and a handy characterization in terms of
edge-colorings of their Hasse diagrams.
Bastian Laubner: The graph isomorphism problem for bounded rank-width
Graph isomorphism is one of the few natural problems that are neither
known to be NP-hard nor to be in PTIME. At the least, the problem can be
solved efficiently on certain classes of graphs, e.g., on graphs of
bounded tree-width or graphs of bounded degree. A similar result is
unknown for classes of bounded rank-width. Rank-width is a
generalization of the well-known tree-width parameter in the spirit of
general branch-width. Its value is closely related to the graph's
clique-width. In this talk I define rank-width and outline the prospects
of combinatorial and group-theoretical approaches to solving graph
isomorphism on classes of bounded rank-width.