0
$\begingroup$

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|$$

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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$).

example

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.