Tsan-sheng Hsu and Ming-Yang Kao
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.