Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | preliminary term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


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  
Gianpaolo Oriolo.



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
hypergraphs.
In this talk we introduce some of these concepts and some open questions.



Daria Schymura: A probabilistic algorithm for approximating the maximal area 
of overlap
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
computed.



Ronald Wotzlaw: Polytope Graphs, Skeleta, and Positive k-Spanning Sets of               
Vectors


==========================================================================


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.



Holger Dell: 
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
algorithms.



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.



Christina Puhl: 
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
restricted.
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
NP-complete. 

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
underlying poset?



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.