TITLES AND ABSTRACTS 9 NOVEMBER:Martin Skutella: Virtual Private Network Design and Tree RoutingsConsider 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 MatricesPartition 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 hypergraphsIn 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 motionsA 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 QuotasConsider 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 ProblemsIn 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 algorithmsFor 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-leafAn 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 ProblemIn 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 PosetsGiven 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 LatticesUpper 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-widthGraph 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.