Results 1 to 2 of 2

Thread: Approximated vertex cover algorithm on random graph

  1. #1
    Newbie
    Joined
    Mar 2015
    From
    USA
    Posts
    17

    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 $\displaystyle n$ I'm trying to find the smallest $\displaystyle p$ so that running the approximation algorithm above on a random graph $\displaystyle G(n,p)$ will give me (with high probability) a vertex cover with a size that is less then 80% from $\displaystyle n$. For example, I run some tests in java with this algorithm implementation and found:

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

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

  2. #2
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    16,216
    Thanks
    3702

    Re: Approximated vertex cover algorithm on random graph

    Quote Originally Posted by gudin727 View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] graph vertex colouring
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 2nd 2010, 10:46 AM
  2. vertex basis for the graph
    Posted in the Geometry Forum
    Replies: 2
    Last Post: Jun 7th 2010, 03:58 AM
  3. Hitting and Cover time, Random Walks on Graphs
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 15th 2010, 06:53 AM
  4. n-vertex graph
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Nov 25th 2009, 10:37 AM
  5. Finding the vertex of the parabolic graph
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Oct 28th 2008, 02:15 PM

Search Tags


/mathhelpforum @mathhelpforum