1
$\begingroup$

Say we have a graph $G=(V,E)$. Each edge $e$ in $E$ has a cost $c > 0$.

Now we want to find a subgraph G'=(V',E') of $G$ such that there is at least $k$ edges, $k>0$, and constant) in G' and total cost the edges in G' is minimized. Up to this point the problem is trivial. Just sort the edges in increasing order and pick lowest $k$ edges.

But the subgraph G' should satisfy the following property:

If $u$ and $v$ is in V' and there is an edge between $u$ and $v$ in $E$ then that edge must be included E'.

So it may happen that we select edge $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$ in the subgraph and edge$(u_1,u_2)$ is added in G' implicitly.

Is there any similar problem in the literature?? Can this problem be solved efficiently? [Approximation Algorithms will do as well. ]

0 Answers 0