An optimization problem on graphs (Q1085182): Difference between revisions

A graph G with vertex set \(X=\cup^{n}_{i=1}X_ i\), for n given sets \(X_ i\), is called a feasible graph for \((X_ 1,...,X_ n)\) if, for each \(X_ i\), the subgraph \(G_ i\), with vertex set \(X_ i\), is connected. The authors consider the (NP-hard) problem of finding a minimum feasible graph. They give a sufficient condition, that can be checked in polynomial time, for a graph to be minimum. In addition, they show how every minimum feasible graph for \((X_ 1,...,X_ n)\) can be obtained from any such graph.