3 ms·
If I go through the list of edges one by one and push the two vertices of each edge into a Set, at the end wouldn’t I end up with the minimum number of vertices
by v_g 6y ago
If I go through the list of edges one by one and push the two vertices of each edge into a Set, at the end wouldn’t I end up with the minimum number of vertices needed to cover the graph?
Most likely I’m not understanding the problem, would appreciate if someone could clarify.
- anonymoushn 6y agoThe minimum vertex cover is a minimal set of vertices such that every edge is incident to at least one vertex in the set. For a star graph with 101 nodes and 100 edges, the minimum vertex cover is a set containing 1 vertex. The algorithm in TFA gives a set containing 2 vertices. Your algorithm gives a set containing a bit more than 2 vertices.
- saagarjha 6y agoYour set would contain all the vertices, while you can do better by only including some. For example, think of three vertices in a line with the first and second vertex joined by and edge and the second and third. The “optimal cover” picks the second vertex and covers both edges.
- thethirdone 6y agoYou only need one of the vertices of an edge to cover that edge. So in the simplest case of two vertices connected by an edge, your algorithm would generate a set of size 2 instead of the minimum size 1.