Graph Augmentation Problems

• IIS members:
  • Tsan-sheng Hsu, IIS, Academia Sinica.
• Outside members:
  • Ming-Yang Kao, Department of Computer Science, Northwestern University.
  • 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 tables.

• 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 $k$-vertex-connected. 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 (Extended Abstract)," 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 augmentation problem. 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.