# An algorithm with Minimum vertex cover without considering its performance - Theory

This is a discussion on An algorithm with Minimum vertex cover without considering its performance - Theory ; eKo1 wrote: &gt; eKo1 wrote: &gt; &gt; Perhaps I'm not understanding what a vertex cover is. I thought a &gt; &gt; vertex cover was just the set of all vertices which are incident to &gt; &gt; edges in E. I ...

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

eKo1 wrote:
> eKo1 wrote:
> > Perhaps I'm not understanding what a vertex cover is. I thought a
> > vertex cover was just the set of all vertices which are incident to
> > edges in E. I guess I'll have to research what a vertex cover is in
> > more detail.

>
> 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.

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.

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.
3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;
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;
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.
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

with the largest degree.
6. a. Delete its input cell;
b. clear the last setting of LargestDegreeEndVertexFlag,
c. for all edge ending vertex cells, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;
b. edge count is decreased by 1;
c. set new LargestDegreeEndVertexFlag
and go to 2.

Why are there 2-4 procedures:
See examples.
1--2--3--4--5
|
6
|
7
When the algorithm reaches procedure 5, it has output:
2, 4, 6 and Count = 3.

8
|
1--2--3--4--5
|
6
|
7
Output: 2, 4, 6 and 8 and Count = 4.

The reason is, no matter what other parts of graph are,
the vertex outputs must include all its branch end terminal.

Now I give a explanation to the procedure 5-6:
5-6: when there are no claws, delete the cell with largest degree;
but at the same time avoid to use the cells that are the end vertexes
of last select cell with largest degree.

Example for largest cell selection:
(5, 1, 2, 3, 4, 5, 6) (vertex 1 has 5 edges)
(5, 2, 3, 4, 5, 6, 1) (vertex 2 has 5 edges)
(4, 7, 2, 3, 4, 5, 6) (vertex 7 has 4 edges)

step 1: It may select vertex 1 or 2; it selects 1:
(5, 2, 3, 4, 5, 6, 1) --> (4, 2, 3, 4, 5, 6)+
step 2:
(4, 2, 3, 4, 5, 6)+
(4, 7, 2, 3, 4, 5)

'+' indicates it was an ending vertex of last selection vertex with
largest degree.

Both have count = 4, but (4, 2, 3, 4, 5, 6)+ was connected to
the last selection vertex 1, so it should select (4, 7, 2, 3, 4, 5).

This method is used to avoid both vertexes on one edge are selected
to create a situation that would increase chance of duplicate vertex
selection.

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

Do you have any smart tips?

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

Thank you.

Weng

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

eKo1 wrote:
> eKo1 wrote:
> > Perhaps I'm not understanding what a vertex cover is. I thought a
> > vertex cover was just the set of all vertices which are incident to
> > edges in E. I guess I'll have to research what a vertex cover is in
> > more detail.

>
> 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.

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.

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.
3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;
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;
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.
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

with the largest degree.
6. a. Delete its input cell;
b. clear the last setting of LargestDegreeEndVertexFlag,
c. for all edge ending vertex cells, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;
b. edge count is decreased by 1;
c. set new LargestDegreeEndVertexFlag
and go to 2.

Why are there 2-4 procedures:
See examples.
1--2--3--4--5
|
6
|
7
When the algorithm reaches procedure 5, it has output:
2, 4, 6 and Count = 3.

8
|
1--2--3--4--5
|
6
|
7
Output: 2, 4, 6 and 8 and Count = 4.

The reason is, no matter what other parts of graph are,
the vertex outputs must include all its branch end terminal.

Now I give a explanation to the procedure 5-6:
5-6: when there are no claws, delete the cell with largest degree;
but at the same time avoid to use the cells that are the end vertexes
of last select cell with largest degree.

Example for largest cell selection:
(5, 1, 2, 3, 4, 5, 6) (vertex 1 has 5 edges)
(5, 2, 3, 4, 5, 6, 1) (vertex 2 has 5 edges)
(4, 7, 2, 3, 4, 5, 6) (vertex 7 has 4 edges)

step 1: It may select vertex 1 or 2; it selects 1:
(5, 2, 3, 4, 5, 6, 1) --> (4, 2, 3, 4, 5, 6)+
step 2:
(4, 2, 3, 4, 5, 6)+
(4, 7, 2, 3, 4, 5)

'+' indicates it was an ending vertex of last selection vertex with
largest degree.

Both have count = 4, but (4, 2, 3, 4, 5, 6)+ was connected to
the last selection vertex 1, so it should select (4, 7, 2, 3, 4, 5).

This method is used to avoid both vertexes on one edge are selected
to create a situation that would increase chance of duplicate vertex
selection.

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

Do you have any smart tips?

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

Thank you.

Weng

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

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

4. ## 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,
I cannot read the page. Can you please post the page on the group or
send me an email?

My email address is wtxwtx at gmail dot com (without space).

I don't know if my algorithm is the same as the one you mentioned.

Actually I checked my algorithm with more than 20 hand-drawn graphs and
all results generated are the minimum vertex cover, no exception!!!

Otherwise I couldn't publish my 2nd version so quickly. If another
error is found, I can also quickly change my design to correct the
error without destroying the full design.

The key point is:
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2. Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3. Repeat 1. and 2. until all input cells are deleted.

I will start writing a program in C and write some programs to generate
random graphs to check if there are any violations:
1. Randomly generate a graph;
2. Generate its minimum vertex cover, m= |V'| by my program.
3. Check C(n, m-1) choices to see if any of them meets the minimum
vertex cover.

I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
It has a problem 35.1-3:
Professor Nixon proposes the following heuristic to solve the
vertex-cover problem. Repeatedly select a vertex of highest degree, and
remove all of its incident edges. Give an example to show that the
professor's heuristic doesn't not have an approximation ratio of 2.
(Hint: Try a bipartite graph with vertexes of uniform degree on the
left and vertexes of varying degree on the right. )

That is exactly what I suggested in my first version. But with the
problem exposed, I changed my strategy to delete any claws first, then
do the selection.

If you can post a graph that fails my algorithm, it will be great!!!

Thank you.

Weng

5. ## Re: An algorithm with Minimum vertex cover without considering itsperformance

Weng Tianxiang wrote:
....
> The key point is:
> 1. First delete all claws until there are no any claws; (Claw is a
> vertex of degree 1).
> 2. Next delete the vertex with largest degree and mark its neighbors to
> keep them from being selected next time unless next time all vertexes
> that have the largest degree are its neighbors. Later if a vertex's
> edge is deleted, the vertex's neighbor mark should be deleted too if
> any.
> 3. Repeat 1. and 2. until all input cells are deleted.

At some stages in all this deleting, you presumably tag some vertices as
being members of the resulting cover. Could you restate the algorithm
making it clear which they are?

Thanks,

Patricia

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

Patricia Shanahan wrote:
> Weng Tianxiang wrote:
> ...
> > The key point is:
> > 1. First delete all claws until there are no any claws; (Claw is a
> > vertex of degree 1).
> > 2. Next delete the vertex with largest degree and mark its neighbors to
> > keep them from being selected next time unless next time all vertexes
> > that have the largest degree are its neighbors. Later if a vertex's
> > edge is deleted, the vertex's neighbor mark should be deleted too if
> > any.
> > 3. Repeat 1. and 2. until all input cells are deleted.

>
> At some stages in all this deleting, you presumably tag some vertices as
> being members of the resulting cover. Could you restate the algorithm
> making it clear which they are?
>
> Thanks,
>
> Patricia

Hi Patricia,
Yes.

1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
output claws's only neighbor vertexes as members of the minimum vertex
cover;

1--2--3--4--5--6--7
|
8
|
9
Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
deleted, vertex 3 become a claw and is deleted, then output vertex 4,
vertex 3's neighbor; vertex 8 become a claw and is deleted, output
vertex 9; vertex 5 is a claw, output vertex 6.
So the minimum vertex cover is:
2, 4, 6, 9. |V'| = 4.

2. Next delete the vertex with the largest degree, output the vertex as
a member of the minimum vertex cover and mark its neighbors to keep
them from being selected next time unless next time all vertexes that
have the largest degree are its neighbors. Later if a vertex's edge is
deleted, the vertex's neighbor mark should be deleted too if any.

(5, 1, 2, 3, 4, 5, 6)
(5, 2, 1, 3, 5, 6, 7)
(5, 3, 1, 2, 4, 5, 6)

Select any one of above 3 vertexes, delete it, it become (when the
first is selected):
(4, 2, 3, 5, 6, 7)+
(4, 3, 2, 4, 5, 6)+

'+' means it is a neighbor of the deleted vertex with the largest
degree. On next selectiono, If one of vertexes of the largest degree
has a neighbor mark, it must not selected unless all vertexes of the
largest degree are the neighbors of deleted vertexes of the largest
degree.

Now any of the two above vertexes can be deleted and output because
both are the neighbors.

3. Repeat 1. and 2. until all input cells are deleted.

If you can list a graph that fails my algorithm, you beat me.

Thank you.

Weng

7. ## Re: An algorithm with Minimum vertex cover without considering itsperformance

Weng Tianxiang wrote:
....
> If you can list a graph that fails my algorithm, you beat me.

I wish my algorithm design professor had taken that attitude. It would
have made homeworks much easier. Instead, he insisted on proofs that my
algorithms gave correct answers, as well as meeting their claimed time
complexity.

Patricia

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

David Ashley wrote:
> Weng Tianxiang wrote:
> > 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,
> > I cannot read the page. Can you please post the page on the group or
> > send me an email?
> >
> > My email address is wtxwtx at gmail dot com (without space).
> >
> > I don't know if my algorithm is the same as the one you mentioned.
> >
> > Actually I checked my algorithm with more than 20 hand-drawn graphs and
> > all results generated are the minimum vertex cover, no exception!!!
> >
> > Otherwise I couldn't publish my 2nd version so quickly. If another
> > error is found, I can also quickly change my design to correct the
> > error without destroying the full design.
> >
> > The key point is:
> > 1. First delete all claws until there are no any claws; (Claw is a
> > vertex of degree 1).
> > 2. Next delete the vertex with largest degree and mark its neighbors to
> > keep them from being selected next time unless next time all vertexes
> > that have the largest degree are its neighbors. Later if a vertex's
> > edge is deleted, the vertex's neighbor mark should be deleted too if
> > any.
> > 3. Repeat 1. and 2. until all input cells are deleted.
> >
> > I will start writing a program in C and write some programs to generate
> > random graphs to check if there are any violations:
> > 1. Randomly generate a graph;
> > 2. Generate its minimum vertex cover, m= |V'| by my program.
> > 3. Check C(n, m-1) choices to see if any of them meets the minimum
> > vertex cover.
> >
> > I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
> > It has a problem 35.1-3:
> > Professor Nixon proposes the following heuristic to solve the
> > vertex-cover problem. Repeatedly select a vertex of highest degree, and
> > remove all of its incident edges. Give an example to show that the
> > professor's heuristic doesn't not have an approximation ratio of 2.
> > (Hint: Try a bipartite graph with vertexes of uniform degree on the
> > left and vertexes of varying degree on the right. )
> >
> > That is exactly what I suggested in my first version. But with the
> > problem exposed, I changed my strategy to delete any claws first, then
> > do the selection.
> >
> > If you can post a graph that fails my algorithm, it will be great!!!
> >
> > Thank you.
> >
> > Weng
> >

>
> Weng,
>
> Did you mean to post this to comp.arch.fpga?
>
> It's an interesting problem and all, but...?
>
> -Dave
>
> --
> David Ashley http://www.xdr.com/dash
> Embedded linux, device drivers, system architecture

Hi David,
Yes, I post it for comp.arch.fpga too.

1. comp.arch.fpga has a group of engineers who have many experiences
with logic design, are talent and should pay attention to the deepest
problem in computing complexity.

2. I dream someday we can design a NP machine that runs all NP problems
in polynomial time using a FPGA chip. Personally I think Turing machine
should be dying with powerful FPGA chips growing and the fact should be
reflected in computing theory.

3. The above posting is my a small step in a direction I am thinking is
right: first to design an algorithm that is not using brute force, but
some smart ideas of the special problem.

4. I select the minimum vertex cover because its memory will never be
expanded and it depends on a smarter selection to finish the cover.

5. At the current moment, I am devoting to design an algorithm that
works with minimum vertex cover.

6. If the algorithm works, all of us have a chance to finish a NP
machine with performance in polynomial time.

Thank you.

jWeng

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

Patricia Shanahan wrote:
> Weng Tianxiang wrote:
> ...
> > If you can list a graph that fails my algorithm, you beat me.

>
> I wish my algorithm design professor had taken that attitude. It would
> have made homeworks much easier. Instead, he insisted on proofs that my
> algorithms gave correct answers, as well as meeting their claimed time
> complexity.
>
> Patricia

Hi Patricia,
1. Yes, I have to prove the following theorem:
If a graph has no claws (vertex of degree 1), the vertex with the
largest degree can be a member of the minimum vertex cover.

2. I am doing the following things:
a. Develop the algorithm in C;
b. Develop an algorithm in C that can generate random graphs;
c. Feed the graphs to my algorithm and generate |V'| data;
d. Enumerate all cover options of C(N, |V'|-1) to confirm that there is
no graph cover with less degrees.

It takes time, but if all people help me, it will be great!

Thank you.

Weng

10. ## Re: An algorithm with Minimum vertex cover without considering itsperformance

[comp.arch.fpga deleted from newsgroups. I don't think my comments are
on-topic there].

Weng Tianxiang wrote:
.....
> 1. First delete all claws until there are no any claws; (Claw is a
> vertex of degree 1).
> output claws's only neighbor vertexes as members of the minimum vertex
> cover;
>
> 1--2--3--4--5--6--7
> |
> 8
> |
> 9
> Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
> 1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
> deleted, vertex 3 become a claw and is deleted, then output vertex 4,
> vertex 3's neighbor; vertex 8 become a claw and is deleted, output
> vertex 9; vertex 5 is a claw, output vertex 6.
> So the minimum vertex cover is:
> 2, 4, 6, 9. |V'| = 4.
>
> 2. Next delete the vertex with the largest degree, output the vertex as
> a member of the minimum vertex cover and mark its neighbors to keep
> them from being selected next time unless next time all vertexes that
> have the largest degree are its neighbors. Later if a vertex's edge is
> deleted, the vertex's neighbor mark should be deleted too if any.
>
> (5, 1, 2, 3, 4, 5, 6)
> (5, 2, 1, 3, 5, 6, 7)
> (5, 3, 1, 2, 4, 5, 6)
>
> Select any one of above 3 vertexes, delete it, it become (when the
> first is selected):
> (4, 2, 3, 5, 6, 7)+
> (4, 3, 2, 4, 5, 6)+
>
> '+' means it is a neighbor of the deleted vertex with the largest
> degree. On next selectiono, If one of vertexes of the largest degree
> has a neighbor mark, it must not selected unless all vertexes of the
> largest degree are the neighbors of deleted vertexes of the largest
> degree.
>
> Now any of the two above vertexes can be deleted and output because
> both are the neighbors.
>
> 3. Repeat 1. and 2. until all input cells are deleted.
>
> If you can list a graph that fails my algorithm, you beat me.

1-2-3
| | |
4-5-6
| | |
7-8-9

There is a four element vertex cover, {2,4,6,8}.

There is no degree one vertex, so the first pick will be 5, the highest
degree vertex in the graph. Once 5 has been picked, you are left with a
loop of eight vertices, and must pick four of them to complete the
cover. The even number vertices are neighbors of 5, so the next pick
will be one of the remaining odd number vertices. After that, step 1
picks odd number vertices, resulting in the five element cover {1,3,5,7,9}.

Even if you tweak your algorithm to deal with this case, remember that
to claim to have a minimum vertex cover you really should be thinking in
terms of proving, for every graph, that your algorithm produces a vertex
cover and no vertex cover can contain fewer vertices.

Patricia

+ Reply to Thread
Page 2 of 4 First 1 2 3 4 Last