Approximating
Graph Orientations With High Rootedconnectivity
By

Professor
Lap Chi Lau

Department
of Computer Science & Engineering

The
Chinese University of Hong Kong



Date:
March 10, 2008 (Monday) 
Time:
4:00pm  5:00 pm 
Venue:
Rm. 1009 William MW Mong Engineering Building,
CUHK 
Abstract
:
We
consider a problem that is motivated by the network
multicating problem. Given an undirected graph and
a subset of vertices S with a specified root vertex
r in S, the Steiner RootedOrientation problem is
to find a direction of all the edges so that in the
resulting directed graph the ``connectivity'' from
the root r to the vertices in S is maximized. This
is motivated by a multicasting problem in undirected
networks as well as a generalization of some classical
problems in graph theory. The main results are the
following approximate minmax relations:
 Given an undirected hypergraph H, if S is 2khyperedgeconnected
in H, then H has a Steiner rooted khyperarcconnected
orientation.

Given an undirected graph G, if S is 2kelementconnected
in G, then G has a Steiner rooted kelementconnected
orientation.
Both
results are tight in terms of the connectivity bounds.
These also give polynomial time constant factor approximation
algorithms for both problems. The proofs are based
on submodular techniques, and a graph decomposition
technique used in the Steiner Tree Packing problem.
