# Thread: Approximated vertex cover algorithm on random graph

1. ## Approximated vertex cover algorithm on random graph

I'm trying to investigate the results of running the follwing factor two algorithm for minimum vertex cover on random graphs:
https://en.wikipedia.org/wiki/Vertex_cover#Pseudo_Code
To be more specific, for a given number of vertices $n$ I'm trying to find the smallest $p$ so that running the approximation algorithm above on a random graph $G(n,p)$ will give me (with high probability) a vertex cover with a size that is less then 80% from $n$. For example, I run some tests in java with this algorithm implementation and found:

For a graph with 60 vertices- $p<9$% will give the desired results.
For a graph with 300 vertices - $p<0.7$% will give the desired results.
For a graph with 3500 vertices - $p<0.3$% will give the desired results.

As it can be seen, the larger the number of vertices - the smaller the number of $p$ needed for my desired results.
My try for explaining those results: since in a graph $G(V,E)$ we know that $|E| = O(V^2)$, if we enlarge $|V|$ then the number of possibilities for edges will be much greater relative to the enlargement of $|V|$. Therefore, if we have graphs $G(n,p), G'(n' , p)$ when $n'>n$ then it's more likely that $G'$ will contain more edges.
Let's denote by $c^*$ and $c'^*$ the minimal vertex cover of $G$ and $G'$, and by $c$ and $c'$ the approximated vertex cover of $G$ and $G'$. Since their edges were randomly selected and we have more edges in $G'$ - it's more likely that $c^*/n < c'^*/n$ and therefore also $c/n < c'/n$.

There are few things I'm not sure about:
1. The last line of the explanation when I wrote that the fact that the edges where randomly selected help us deduce the desired results. Is my explanation correct?
2. It seems that my results are relating to a general vertex cover, and are not specific only for the approximated algorithm. Am I right here?

2. ## Re: Approximated vertex cover algorithm on random graph

Originally Posted by gudin727
I'm trying to investigate the results of running the follwing factor two algorithm for minimum vertex cover on random graphs:
https://en.wikipedia.org/wiki/Vertex_cover#Pseudo_Code
To be more specific, for a given number of vertices $n$ I'm trying to find the smallest $p$ so that running the approximation algorithm above on a random graph $G(n,p)$ will give me (with high probability) a vertex cover with a size that is less then 80% from $n$. For example, I run some tests in java with this algorithm implementation and found:

For a graph with 60 vertices- $p<9$% will give the desired results.
For a graph with 300 vertices - $p<0.7$% will give the desired results.
For a graph with 3500 vertices - $p<0.3$% will give the desired results.

As it can be seen, the larger the number of vertices - the smaller the number of $p$ needed for my desired results.
My try for explaining those results: since in a graph $G(V,E)$ we know that $|E| = O(V^2)$, if we enlarge $|V|$ then the number of possibilities for edges will be much greater relative to the enlargement of $|V|$. Therefore, if we have graphs $G(n,p), G'(n' , p)$ when $n'>n$ then it's more likely that $G'$ will contain more edges.
Let's denote by $c^*$ and $c'^*$ the minimal vertex cover of $G$ and $G'$, and by $c$ and $c'$ the approximated vertex cover of $G$ and $G'$. Since their edges were randomly selected and we have more edges in $G'$ - it's more likely that $c^*/n < c'^*/n$ and therefore also $c/n < c'/n$.

There are few things I'm not sure about:
1. The last line of the explanation when I wrote that the fact that the edges where randomly selected help us deduce the desired results. Is my explanation correct?
2. It seems that my results are relating to a general vertex cover, and are not specific only for the approximated algorithm. Am I right here?
as a courtesy, edited out "tex" tags (they are inoperable at the moment ... no clue why) and replaced them with \\$ tags