My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
December 13th, 2017, 10:58 AM   #1
Joined: Mar 2015
From: USA

Posts: 33
Thanks: 1

Approximated vertex cover algorithm on random graph

I'm trying to investigate the results of running the following factor two algorithm for minimum vertex cover on random graphs.
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?
Lobinho is offline  

  My Math Forum > Science Forums > Computer Science

algorithm, approximated, cover, graph, random, vertex

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
How many mathematics textbooks is it realistic to study cover to cover mathsman1 Math 3 November 30th, 2015 12:37 PM
Standard form and identify the vertex of a graph kayna84 Pre-Calculus 1 July 30th, 2015 12:44 PM
Hamiltonian Algorithm for n vertex complete graph vinaychaturvedi Computer Science 0 April 25th, 2012 04:45 AM
Number of ways to make a graph from n-size vertex set Singularity Applied Math 1 April 15th, 2011 07:42 AM
Weighted Vertex Cover on Bipartite Graph - NP-hard? hkoehler Computer Science 0 May 16th, 2010 08:37 PM

Copyright © 2018 My Math Forum. All rights reserved.