Optimal Bi-Level Augmentation for Selectively Enhancing Graph Connectivity with Applications

Tsan-sheng Hsu and Ming-Yang Kao

TR-IIS-96-011 (Fulltext)

graph augmentation, graph connectivity, data security, network reliability


Our main problem is abstracted from several optimization problems for protecting information in cross tabulated tables and for improving the reliability of communication networks. Given an undirected graph $G$ and two vertex subsets $H_1$ and $H_2$, the {\it smallest bi-level augmentation problem} is that of adding to $G$ the smallest number of edges such that $G$ contains two internally vertex-disjoint paths between every pair of vertices in $H_1$ and two edge-disjoint paths between every pair of vertices in $H_2$. We give a data structure to represent essential connectivity information of $H_1$ and $H_2$ simultaneously. Using this data structure, we solve the bi-level augmentation problem in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices and edges in $G$. Our algorithm can be parallelized to run in $O(\log^2 n)$ time using $n+m$ processors on an EREW PRAM. By properly setting $G$, $H_1$ and $H_2$, our augmentation algorithm also subsumes several existing optimal algorithms for graph augmentation.