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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.