Re: An algorithm with Minimum vertex cover without considering its performance


Arthur J. O'Dwyer wrote:
On Sun, 24 Sep 2006, Weng Tianxiang wrote:
eKo1 wrote:

Let V' be a subset of V. V' is a vertex cover if it satisfies the
following test:

E' = Ø
for each v in V'
for each edge e in E
if v is incident to e then
add e to E'
end if
end for
end for
if |E| = |E'| then
return true // V' is a vertex cover
end if
return false

Would this be correct?

Hi eKo1,
The algorithm you mentioned for a vertex cover is right.

Yes, that's right. (And it suggests a trivial brute-force algorithm
to find a minimum vertex cover:

M = V
for each V' in V
if (V' is a vertex cover of G) then
if |V'| < |M| then
M = V
end if
end if
end for
return M

Now M is a minimum vertex cover.)


Here is my full new algorithm that can get minimum vertex cover:

To make discussion simpler, we assume that every vertex has a positive
integer, starting with 1 to n and input cells have the following
structure:
(edge count, edge starting vertex, edge ending vertexes).

For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell has the following representation: (3, 1, 2, 3, 4). Cell length
vary dependent on the cell's degree, or the number of edges which is
incident on the cell.

Whoof, that's a clumsy representation! Next time, consider using a
more natural representation, such as "Each vertex has a list of
neighbors. For example, vertex 1 has neighbors {2,3,4}."

Here is new full algorithm to get minimum vertex cover:
1. Count = 0.
2. If input cell is empty, algorithm ends, otherwise
Sort the input cell serials based on count in increasing order.

What are the "input cell serials"? I'm guessing you mean to sort the
cells in increasing order by degree, i.e., the cells with lower degree
come first in the list. Okay, but let me know if I'm wrong.

3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;

What?

b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;

What?

b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex and go to b.
d. if edge count = 0, delete the cell;
4. If input cell is empty, algorithm ends, otherwise
sort the input cell serials based on count in decreasing order.

What? What is the "input cell"? What is an "empty" cell --- is ()
the only empty cell, or could (0, 5) be considered empty too?

5. If there is only one cell that has the largest degree, select the
cell
and go to 6. If there are more than one cell that have the equal
largest degree, select the cell that has not been the end vertex
of the last selected cell with the largest degree, or select any of
them
if all of them have have been the end vertexes of last selected cell

What? What?

(snip much more gibberish)

Manually I tried more than 20 graphs and get the right answers for
every graph.

Good for you.

Do you have any smart tips?

Yes. Stop trying to find a polynomial algorithm for minimum vertex
cover until you've read at least one existing (non-polynomial) algorithm
and understand how it works. Also, try to write in plain English, or,
failing that, some common programming language.

If you can find a graph that fails the algorithm, please let me know.

Yes, I can. So now you know.

-Arthur

Hi Arthur,
Your help is very much appreciated.

Yes, I am trying to read as many papers as possible about algorithms
with minimum vertex cover. But most of them are dealing with
approximation approach that I am not interested in.

Can you point to any papers about non-approximation approach and
non-brute force approach?

Thank you.

Weng

.

Relevant Pages