Graph Augmentation Problems
- IIS members:
- Outside members:
Ming-Yang Kao, Department of Computer Science,
- Wei-Kuan Shih, Department of Computer Science,
National Tsing-Hua University.
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.
- Pei-Chi Huang, Hsin-Wen Wei, Wan-Chen Lu, Wei-Kuan Shih
and Tsan-sheng Hsu,
"Smallest Bipartite Bridge-connectivity Augmentation,"
Algorithmica, 2007, accepted.
This paper addresses two augmentation problems related to bipartite
graphs. The first, a fundamental graph-theoretical problem, is how
to add a set of edges with the smallest possible cardinality so that
the resulting graph is 2-edge-connected, i.e., bridge-connected, 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 multi-graph. Our approach then determines whether or
not such an augmentation is possible.
Tsan-sheng Hsu and Ming-Yang Kao,
"Optimal Augmentation for Bipartite Componentwise Biconnectivity
in Linear Time,"
SIAM Journal on Discrete Mathematics, volume 19,
number 2, pages 345--362, 2005.
- A graph is componentwise biconnected if every connected
component either is an isolated vertex or is biconnected. We present
a linear-time 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
- Tsan-sheng Hsu,
"Simpler and Faster Biconnectivity Augmentation,"
Journal of Algorithms,
volume 45, number 1, pages 55--71, 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., 2-vertex-connected, 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.
- Tsan-sheng Hsu, ``On Four-Connecting a Triconnected Graph,''
Journal of Algorithms, volume 35, pages 202--234, 2000.
Extended abstract in
Proc. 33rd Annual IEEE Conf.
on Foundations of Computer Science (FOCS), pages 70--79, 1992.
This paper studies the problem of requiring the graph to be
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 3-vertex-connected.
- Tsan-sheng Hsu,
"Simpler and Faster Vertex-Connectivity Augmentation Algorithms
Proc. 8th European Symposium on Algorithms (ESA) ,
Springer-Verlag LNCS# 1879, pages 278--289, 2000.
Recently, I have discovered a new approach in solving the
Previously, all exact solutions to the vertex-connectivity 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 non-trivial to implement or parallelize
the algorithms. There is only one
parallel algorithm known previously for making
the graph 2-vertex 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 multi-set. Our algorithm solves the 2-vertex-connectivity 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 3-vertex-connectivity case,
though it is a bit more complicated.
We have recently finished the revision of a journal version
for the 2-vertex-connectivity case
for this paper by further simplifying the approach
and will be submitting it soon.
We are still working on further simplifying the 3-vertex-connectivity case
for the journal version.
Updated April 20, 2009.
Created by Tsan-sheng Hsu, last updated April 18, 2001.