A special case for subset interconnection designs Original Research Article

Given a set X and subsets X1, …, Xm, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1,…,m, the subgraph G, induced by Xi is connected. We show that in the special case that every point in X appears in at most three Xiʹs, the problem is still MAX SNP-complete; however, there exists a polynomial-time approximation within a factor of 53 from optimal. As an intermediate result, we also show that the vertex cover problem in cubic graphs is MAX SNP-completc.