i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to.

not sure on how to do it correctly, here's my attempt:

for a given undirected graph $G=(V,E)$ and a vertex $v \in G$

1)$edges \leftarrow \emptyset $

2)remove adjacent edges to given vertex v(given in the input)

3)while there are edges in graph G:

3.1)$edges \leftarrow {u,v}$

3.2)$G\:\leftarrow \:G\:\:\ \:\:\left\{u,v\right\}$ (doesn't let me mark it correctly, but i meant remove {u,v} from G. doesn't give me to write \ correctly

3.3)return |x|+1 (including v we got from the input)

how to make it better? would appreciate seeing better algorithms for this and explanations/insights so i can learn

thank you for your efforts

  • 4
    $\begingroup$ What are your requirements? Are you looking for a polynomial time algorithm? Are you aware that the problem is NP-hard? Why have you rejected your algorithm? Have you tried to prove your algorithm correct? I can't understand steps 3.1-3.3, so I suggest learning how Mathjax works and then revising your question to correct the typesetting. Thank you! $\endgroup$ – D.W. Feb 17 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.