I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ iff they are vertex cover of $G'$.
I understood that a polynomial algorithm exists, it's mean without finding the vertex cover of $G$, but I found only a non-polynomial one.

  • $\begingroup$ I thought about edge cover, maybe this is the solution? $\endgroup$ Feb 25, 2021 at 7:49
  • $\begingroup$ No, I checked it and it looks like not related to edge cover $\endgroup$ Feb 25, 2021 at 9:04

1 Answer 1


The algorithm to compute $G'$ is really easy: just return $G$.

Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.

To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.

Proof that $E \subseteq E'$: Suppose towards a contradiction that $E \nsubseteq E'$. Then $\exists (u,v) \in E \setminus E'$. The set $U = V \setminus \{u,v\}$ is a vertex cover for $G'$ but not for $G$.

Proof that $E' \subseteq E$: Suppose towards a contradiction that $E' \nsubseteq E$. Then $\exists (u,v) \in E' \setminus E$. The set $U = V \setminus \{u,v\}$ is a vertex cover for $G$ but not for $G'$.

  • $\begingroup$ I'm not sure that you're right, a basic example, cube with one additional vertex. G={V,E}, V={1,2,3,4,5}, E={{1,2},{2,3},{3,4}.{4,5}, {5,2}}, have only one vertex cover U={2,4} same as E'={{1,2},{2,3},{3,4},{4,5}}. $\endgroup$ Feb 25, 2021 at 23:54
  • 1
    $\begingroup$ The are many vertex covers of your example graph. A trivial one different from $\{2,4\}$ is $V$ itself. $\endgroup$
    – Steven
    Feb 25, 2021 at 23:56
  • $\begingroup$ Thanks, I'll check how the original question was defined but only tomorrow. Are solution right but too trivial. $\endgroup$ Feb 26, 2021 at 0:02
  • $\begingroup$ Thank you @Steven, but I think you wrong. $G=\{V,E\}, V=\{1,2,3,4\}, E=\{ \{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\},\{2,4\}\}$ have same vertex cover as $E'=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$ or I missed something $\endgroup$ Feb 26, 2021 at 10:46
  • 1
    $\begingroup$ @ChaosPredictor. It's never stated in your question that $G'$ must be a subgraph of $G$, so I didn't assume it. $\endgroup$
    – Steven
    Feb 27, 2021 at 21:15

Your Answer

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

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