Oliver M. Riordan - University of Cambridge

Steiner trees in random graphs

Abstract:   Given a graph with weights or costs associated to the edges, the Steiner tree problem is to find the minimum cost subtree connecting a given set of k vertices. For general graphs this problem is NP-complete. As with other combinatorial optimization problems it is interesting, and relevant for practical applications, to consider not worst case instances, but random instances. The simplest and most natural random example is to take a complete graph on n vertices where the edge costs are independent exponentials with mean 1. We show that for any 2 \le k=o(n) the minimum cost tree connecting k given vertices has cost asymptotic to (k-1/n)(log n-log k).

Two special cases of this problem have been studied previously: Davis and Prieditis and Janson found the minimum cost of a path connecting two given vertices (the case k=2) and Frieze the minimum cost of a spanning tree (k=n). In both cases there is a polynomial time algorithm whose behaviour on the random graph can be analyzed to obtain the result. For general k this is not the case and different methods must be used. A corollary of our result is that whenever k=o(n) an asymptotically optimal spanning tree can be found in polynomial time.

All new results described are joint work with Béla Bollobás, David Gamarnik and Benny Sudakov.

Colloquium - 16 Uhr s.t.

Piotr Krysta - Max-Planck-Institut für Informatik, Saarbrücken

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems

Abstract:   We study the approximability of dense and sparse instances of the following problems: the minimum 2-edge-connected (2-EC) and 2-vertex-connected (2-VC) spanning subgraph, metric TSP with distances 1 and 2 (TSP(1,2)), maximum path packing, and the longest path (cycle) problems. The approximability of dense instances of these problems was left open in a paper of Arora et al. (1995). We resolve the approximability of these problems by proving tight upper (approximation algorithms) and lower bounds (inapproximability). We prove that 2-EC, 2-VC and TSP(1,2) problems are Max-SNP-hard, even on 3-regular graphs, and provide explicit hardness constants, under the usual P \not = NP assumption. We also improve the approximation ratio for 2-EC and 2-VC on graphs with maximum degree 3. These are the first known explicit hardness results on sparse and dense graphs for some of these problems. We also apply our results to prove bounds on the integrality gaps of LP relaxations for 2-EC and TSP(1,2) dense and sparse problems, related to the metric TSP conjecture, due to Goemans (1995).

This is joint work with Bela Csaba and Marek Karpinski.