Vertex Cover implementation - Theory

Francois Delbot <francois.delbot> wrote:
> dear all,
>
> i code this simple greedy algorithm for the vertex cover :
>
> let G be a graph
> C=empty set
> while the number of edges in G is not 0 do
> select the vertex u with maximum degree
> C=C+{u}
> delete u from G
> end while
> return the vertex cover C
>
> so, my code work perfectly but now i want to improve the speed of my
> implementation because i have to do a lot of executions of this
> algorithm.
>
> when i select the vertex u with maximum degree, there can be a lot of
> vertices of maximum degree and i make a list of them, and then, i
> select a vertex at random. this step look very costly.
>
> did you know how i can improve the speed of this algorithm,
> did you know wich structure of graph i have to use to make this
> algorithm more speedy ?

Use a Fibonacci heap. It will reduce the running time of your
implementation to O(|E| + |V| log |V|).

On Jul 28, 4:09 pm, Francois Delbot <francois.del...> wrote:
> dear all,
>
> i code this simple greedy algorithm for the vertex cover :
>
> let G be a graph
> C=empty set
> while the number of edges in G is not 0 do
> select the vertex u with maximum degree
> C=C+{u}
> delete u from G
> end while
> return the vertex cover C
>
> so, my code work perfectly but now i want to improve the speed of my
> implementation because i have to do a lot of executions of this
> algorithm.
>
> when i select the vertex u with maximum degree, there can be a lot of
> vertices of maximum degree and i make a list of them, and then, i
> select a vertex at random. this step look very costly.

It shouldn't be that costly. Each vertex can have a field for its
degree. As you are constructing your graph you can update the vertex
degrees. To find the maximum degree vertices requires only a single
pass through your list/array of vertices. When you remove an edge,
you can decrement the degree of the corresponding vertices.

> did you know how i can improve the speed of this algorithm,
> did you know wich structure of graph i have to use to make this
> algorithm more speedy ?

You could augment the standard adjacency list representation. With
undirected graphs (vertex cover is defined only for undirected
graphs), each edge appears on two adjacency lists. You could have
these edge records point to each other; you can set these pointers as
you build your initial graph. Now suppose you are deleting the edges
adjacent to some vertex a and the current edge on a's list is a--b. We
can immediately find the corresponding edge on b's list by following
our additional pointer and thus avoid having to traverse b's list to
find it! To be able to delete this edge from the middle of b's list
given only a pointer to it, we have to make the adjacency lists doubly-
linked. This should speed things up.

I would ignore the suggestion to use fibonacci heaps. This is a data
structure that implements a "priority-queue" and I don't see a good
reason to use a priority queue for your algorithm.

GCRhoads <GCRhoads@volcanomail.com> wrote:
> On Jul 28, 4:09 pm, Francois Delbot <francois.del...> wrote:
> > dear all,
> >
> > i code this simple greedy algorithm for the vertex cover :
> >
> > let G be a graph
> > C=empty set
> > while the number of edges in G is not 0 do
> > select the vertex u with maximum degree
> > C=C+{u}
> > delete u from G
> > end while
> > return the vertex cover C
> >
> > so, my code work perfectly but now i want to improve the speed of my
> > implementation because i have to do a lot of executions of this
> > algorithm.
> >
> > when i select the vertex u with maximum degree, there can be a lot of
> > vertices of maximum degree and i make a list of them, and then, i
> > select a vertex at random. this step look very costly.
>
> It shouldn't be that costly. Each vertex can have a field for its
> degree. As you are constructing your graph you can update the vertex
> degrees. To find the maximum degree vertices requires only a single
> pass through your list/array of vertices. When you remove an edge,
> you can decrement the degree of the corresponding vertices.

Finding the maximum-degree vertex takes linear time.

> > did you know how i can improve the speed of this algorithm,
> > did you know wich structure of graph i have to use to make this
> > algorithm more speedy ?
>
> You could augment the standard adjacency list representation. With
> undirected graphs (vertex cover is defined only for undirected
> graphs), each edge appears on two adjacency lists. You could have
> these edge records point to each other; you can set these pointers as
> you build your initial graph. Now suppose you are deleting the edges
> adjacent to some vertex a and the current edge on a's list is a--b. We
> can immediately find the corresponding edge on b's list by following
> our additional pointer and thus avoid having to traverse b's list to
> find it! To be able to delete this edge from the middle of b's list
> given only a pointer to it, we have to make the adjacency lists doubly-
> linked. This should speed things up.
>
> I would ignore the suggestion to use fibonacci heaps. This is a data
> structure that implements a "priority-queue" and I don't see a good
> reason to use a priority queue for your algorithm.

Because it's not as slow as your suggestion. Doing a linear scan per
pass will make the algorithm as a whole cost O(|V|^2) time, as opposed
to the O(|E| + |V| log |V|) time bound you get by using a Fibonacci heap
to remember which vertex has highest degree. Any other reasonable data
structure (heaps, tournament trees...) for priority queues will give you
an O(|E| log |V|) algorithm, which is almost the same.

On Jul 30, 8:08 pm, Tor Myklebust <tmykl...@csclub.uwaterloo.ca>
wrote:
> GCRhoads <GCRho...@volcanomail.com> wrote:
> > On Jul 28, 4:09 pm, Francois Delbot <francois.del...> wrote:
> > > dear all,
>
> > > i code this simple greedy algorithm for the vertex cover :
>
> > > let G be a graph
> > > C=empty set
> > > while the number of edges in G is not 0 do
> > > select the vertex u with maximum degree
> > > C=C+{u}
> > > delete u from G
> > > end while
> > > return the vertex cover C
>
> > > so, my code work perfectly but now i want to improve the speed of my
> > > implementation because i have to do a lot of executions of this
> > > algorithm.
>
> > > when i select the vertex u with maximum degree, there can be a lot of
> > > vertices of maximum degree and i make a list of them, and then, i
> > > select a vertex at random. this step look very costly.
>
> > It shouldn't be that costly. Each vertex can have a field for its
> > degree. As you are constructing your graph you can update the vertex
> > degrees. To find the maximum degree vertices requires only a single
> > pass through your list/array of vertices. When you remove an edge,
> > you can decrement the degree of the corresponding vertices.
>
> Finding the maximum-degree vertex takes linear time.
>
>
>
> > > did you know how i can improve the speed of this algorithm,
> > > did you know wich structure of graph i have to use to make this
> > > algorithm more speedy ?
>
> > You could augment the standard adjacency list representation. With
> > undirected graphs (vertex cover is defined only for undirected
> > graphs), each edge appears on two adjacency lists. You could have
> > these edge records point to each other; you can set these pointers as
> > you build your initial graph. Now suppose you are deleting the edges
> > adjacent to some vertex a and the current edge on a's list is a--b. We
> > can immediately find the corresponding edge on b's list by following
> > our additional pointer and thus avoid having to traverse b's list to
> > find it! To be able to delete this edge from the middle of b's list
> > given only a pointer to it, we have to make the adjacency lists doubly-
> > linked. This should speed things up.
>
> > I would ignore the suggestion to use fibonacci heaps. This is a data
> > structure that implements a "priority-queue" and I don't see a good
> > reason to use a priority queue for your algorithm.
>
> Because it's not as slow as your suggestion. Doing a linear scan per
> pass will make the algorithm as a whole cost O(|V|^2) time, as opposed
> to the O(|E| + |V| log |V|) time bound you get by using a Fibonacci heap
> to remember which vertex has highest degree. Any other reasonable data
> structure (heaps, tournament trees...) for priority queues will give you
> an O(|E| log |V|) algorithm, which is almost the same.

The time bound for a Fibonacci heap is an *amortized* bound not a
worst case bound. In practice, it performs worse than other priority
queue data structures (e.g. binary heaps); the constants hidden by the
O notation are higher (since there is more work to do per operation).
The best *worst* case bound is indeed O(|E| log |V|). Whether this is
better than the linear scan depends on how dense the graph is. Most
graphs are pretty sparse so it is probably better asymptotically but
even so it might not be better for whatever size graphs the O.P. is
working with. The steps taken by the linear scan method are so simple
that it is going to have smaller constants; the decrease steps are
particularly trivial for this method. Hence the asymptotically faster
method may not be faster in practice until the graph gets extremely
large. You may be correct, a priority queue may lead to a faster
program but to convincingly demonstrate this, somebody is going to
have to code it up both ways and test how they perform on graphs of
various sizes and densities. I've never read about any such
simulation but perhaps you have.

Dear all,
thank you for your help. I will code both methods and i will give you
my results...
but i can't do that this week, so i will do it next week.

if you have some hints to improve the speed of one of these methods,
i'm very interested.


thank you very much.

francois delbot

GCRhoads <GCRhoads@volcanomail.com> wrote:
> The time bound for a Fibonacci heap is an *amortized* bound not a
> worst case bound.

"Insert takes amortized constant time" and "update takes amortized
constant time" and "extract-min takes amortized O(log n) time" mean
that the running time of any sequence of i insertions, u updates,
and e extract-min's is O(i + u + e log(i+u+e)). We do |V| insertions,
|E| updates, and |V| extract-min's, hence we take
O(|E| + |V| log (|V| + |E|)) = O(|E| + |V| log |V|) time.