# Minimum spanning tree where weights of edges are intersecting sets

Given Graph $$G=(V, E)$$, where each edge in $$E$$ is assigned a "weight" as a set of elements. $$w(e) = S_e \ \forall e \in E$$.

Find a subset $$E' \subset E$$ such that it spans $$G$$, i.e., $$E'$$ connects all pairs of nodes $$n_1, n_2 \in V$$ through some path, such that its "total weight", the size of the union of all of its member's weights is minimized:

$$\min_{E'} \ \ w(E') = \left|\bigcup_e S_e\right|$$

The problem is NP-hard even when all sets have at most (or exactly) one element. This can be seen by a reduction from (the decision version of) vertex cover. Given graph $$H$$, you can build the graph $$G=(V,E)$$ by starting with a graph containing a single vertex $$s$$ and doing the following for each $$e=(u,v)$$ of $$H$$:

• Add three new vertices to $$G$$ namely $$x_e, y_e$$ and $$z_e$$.
• Add the edge $$(y_e, x_e)$$ with "weight" $$S_{(y_e, x_e)}=\{u\}$$.
• Add the edge $$(y_e, z_e)$$ with "weight" $$S_{(y_e, z_e)}=\{v\}$$.
• Add the edges $$(s, x_e)$$ and $$(s, z_e)$$, both with "weight" $$\emptyset$$.

Let $$E'$$ be an optimal solution to your problem on $$G$$. I clam that $$S=\bigcup_{e \in E'} S_e$$ is a vertex cover of $$H$$. Indeed, suppose that there is some edge $$e=(u,v)$$ of $$H$$ that is not covered by $$S$$. This means that $$\{u,v\} \cap S = \emptyset$$ implying $$(y_e, x_e) \not\in E'$$ and $$(y_e, z_e) \not \in E'$$. Since $$(y_e, x_e)$$ and $$(y_e, z_e)$$ are the only edges incident to $$y_e$$ in $$G$$, we conclude that $$E'$$ does not induce a spanning tree of $$G$$.

On the other hand, if $$S$$ is a vertex cover for $$H$$ then there exists a solution $$E'$$ to your problem with measure at most $$|S|$$. Simply select $$E'$$ as any spanning tree of the the subgraph of $$G$$ induced by the union of (i) all the edges incident to $$s$$, and (ii) all edges $$e=(y_e, u)$$ with $$S_e \cap S \neq \emptyset$$.

Here is an example (solid vertices form a vertex cover of $$H$$, bold edges induce a MST of $$G$$). If you want all sets to have cardinality $$1$$ you can change the "weight" of the edges $$(s, x_e)$$ and $$(s, z_e)$$ from $$\emptyset$$ to $$\{s\}$$ and slightly modify the above arguments.