Graph Augmentation Problems
Participants,
Overview,
Selected results.
Participants
 IIS members:
 Outside members:

MingYang Kao, Department of Computer Science,
Northwestern University.
 WeiKuan Shih, Department of Computer Science,
National TsingHua University.
Overview
A graph is $k$vertex (edge, respectively) connected if
you cannot disconnect the graph by removing less than
$k$ vertices (edges, respectively) from the graph.
The graph augmentation problem is the problem of adding
as few edges as possible to the graph such that
the resulting graph satisfies a given connectivity requirement.
This is a very fundamental graph theoretical problem which has
applications in designing reliable networks,
drawing graphs, protecting statistical databasea ... etc.
Selected results
 PeiChi Huang, HsinWen Wei, WanChen Lu, WeiKuan Shih
and Tsansheng Hsu,
"Smallest Bipartite Bridgeconnectivity Augmentation,"
Algorithmica, 2007, accepted.

This paper addresses two augmentation problems related to bipartite
graphs. The first, a fundamental graphtheoretical problem, is how
to add a set of edges with the smallest possible cardinality so that
the resulting graph is 2edgeconnected, i.e., bridgeconnected, and
still bipartite. The second problem, which arises naturally from
research on the security of statistical data, is how to add edges so
that the resulting graph is simple and contains no bridges.
In both cases, after adding edges, the graph can be either a simple graph
or, if necessary, a multigraph. Our approach then determines whether or
not such an augmentation is possible.

Tsansheng Hsu and MingYang Kao,
"Optimal Augmentation for Bipartite Componentwise Biconnectivity
in Linear Time,"
SIAM Journal on Discrete Mathematics, volume 19,
number 2, pages 345362, 2005.
 A graph is componentwise biconnected if every connected
component either is an isolated vertex or is biconnected. We present
a lineartime algorithm for the problem of adding the smallest number
of edges to make a bipartite graph componentwise biconnected while
preserving its bipartiteness. This algorithm has immediate
applications for protecting sensitive information in statistical
tables.
 Tsansheng Hsu,
"Simpler and Faster Biconnectivity Augmentation,"
Journal of Algorithms,
volume 45, number 1, pages 5571, 2002.

This paper presents a new and simple technique to solve
the problem of adding a minimum number of edges
to an undirected graph in order to obtain a
biconnected, i.e., 2vertexconnected, resulting graph.
Our technique results in a simpler algorithm,
which runs in sequential linear time,
that is also faster in parallel than the previous result.
 Tsansheng Hsu, ``On FourConnecting a Triconnected Graph,''
Journal of Algorithms, volume 35, pages 202234, 2000.
Extended abstract in
Proc. 33rd Annual IEEE Conf.
on Foundations of Computer Science (FOCS), pages 7079, 1992.

This paper studies the problem of requiring the graph to be
$k$vertexconnected.
For $k<4$, a trivial lower bound for the number of edges
needed to add is known. This lower bound turns out to be
the exact number of edges needed.
This lower bound does not for $k > 3$.
This paper discovered a new lower bound for $k=4$.
We also prove the lower bound is tight when the input
graph is 3vertexconnected.
 Tsansheng Hsu,
"Simpler and Faster VertexConnectivity Augmentation Algorithms
(Extended Abstract),"
Proc. 8th European Symposium on Algorithms (ESA) ,
SpringerVerlag LNCS# 1879, pages 278289, 2000.

Recently, I have discovered a new approach in solving the
augmentation problem.
Previously, all exact solutions to the vertexconnectivity augmentation
problem require the usage of a dynamic data structure to maintain
a tree when edges are added one at a time and the sorting routine.
Hence it is nontrivial to implement or parallelize
the algorithms. There is only one
parallel algorithm known previously for making
the graph 2vertex connected.
In this paper, we report an approach
that totally gets rid of the usage of
dynamic data structure and sorting. Instead, we only need to compute
various simple functions on trees and the find a maximum element
in a multiset. Our algorithm solves the 2vertexconnectivity augmentation
by adding all needed edges in $O(1)$ iterations. Previous approaches
add one edge at a time, and add the next edge depending on the
maintained dynamic data structure.
This approach can be generalized to solve the 3vertexconnectivity case,
though it is a bit more complicated.
We have recently finished the revision of a journal version
for the 2vertexconnectivity case
for this paper by further simplifying the approach
and will be submitting it soon.
We are still working on further simplifying the 3vertexconnectivity case
for the journal version.
Updated April 20, 2009.
Created by Tsansheng Hsu, last updated April 18, 2001.