Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$:
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.
