A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) given a set X and subsets Xi, Yi of X, i=1,...,n, satisfying XiℝYi=0ab23/, find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by Xz.drule;Yi has a connected component containing Xi. Two other problems related to this one are the following ones. (2) Given a set X and subsets X1,X2,...,Xn such that X=¸ℝnab22iÅ=1Xi, find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph Gi induced by Xi in G is connected. (3) Given a set X and subsets X1,X2,...,Xn such that X=¸ℝnab22iÅ=1Xi, find a graph G with vertex set X and the minimum number of edges such that for any subset I of {1,...,n}, the subgraph induced by ¸ℝiÅ∈1Xi is connected. This paper shows that (3) is polynomial-time solvable while (1) and (2) are NP-complete. Also, some heuristics for (1) and (2) are given. The solution of (3) is an interesting application of matroid theory.
