Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. ]

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.