I was studying Meet-in-the-Middle algorithm and found the following exercise:
Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the graph has at least one node inside the set.
I have no idea how to do that, only hint I got was
complexity O(3^(n/2))
can you explain the idea?
Take out an edge (u1, v1) from the graph, remove all edges that share a vertex with it. Take out another one (u2, v2), ... continue until the rest of the graph has no edges.
You end up with a number of pairs of vertices
(u1, v1), (u2, v2), ..., (uk, vk)
The rest of the vertices are:
w1, w2, ..., wm
Call the first set of vertices paired vertices, and the second set unpaired vertices. Note, 2k + m = n, there are no edges between unpaired vertices in the original graph.
A vertex cover must have either u1, v1, or both in it. There are 3 choices for each pair (uj, vj). Consider all 3^k ways to include the paired vertices to the vertex cover.
For each of those configurations, an unpaired vertex wi is to be included into the cover if and only if at least one of its neighbors is not in the cover (note that each of wi's neighbors are paired vertices so whether they are included is known).
For each of the 3^k selections of paired vertices, include the unpaired vertices according to the above criteria, then verify each edge between paired vertices has an incident vertex from the cover, if so, it is a candidate cover set. Take one of the candidate cover sets of minimum size as output.
Overall complexity of the above algorithm is O(3^(n/2)E) where E is the number of edges in the graph.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments