Given an undirected graph G = (V, E), a subset S of V is called a vertex cover,
ID: 3693554 • Letter: G
Question
Given an undirected graph G = (V, E), a subset S of V is called a vertex cover, if for every edge <u, v> ? E, at least one of u or v belongs to S.
Given an undirected graph G = (V, E), a subset S of V is called a vertex cover, if for every edge (u, v) E E, at least one of u or v belongs to S. Let T be a binary tree. Give a O(n) time dynamic programming algorithm that computes the smallest size vertex cover of T. Prove the correctness of the algorithm and derive the time bound. Here n is number of vertices of the tree.Explanation / Answer
A vertex cover is a set of marked vertices in a graph that covers every edge; in a tree this means that every node or its parent is marked. A minimum vertex cover is a vertex cover that marks the fewest nodes.
Here's a recursive algorithm for finding the size of a minimum vertex cover in a tree, based on the very simple fact that the root must either be put in or not:
VC(root, mustIncludeRoot):
if mustIncludeRoot:
return 1 + sum over all children of VC(child, false)
else:
withRoot = 1 + sum over all children of VC(child, false)
withoutRoot = sum over all children of VC(child, true)
return min(withRoot, withoutRoot)
The running time of this algorithm depends on the structure of the tree in a complicated way, but we can easily see that it will grow at least exponentially in the depth. This is a job for dynamic programming.
The dynamic programming version computes both VC(root, false) and VC(root, true) simultaneously, avoiding the double call for each child. The structure of the resulting algorithm does not look much like the table structures we typically see elsewhere, but the pairs of values passed up through the tree are in fact acting as very small vestigial tables.
DynamicVC(root):
for each child c:
Best[c][0], Best[c][1] = DynamicVC(c)
withoutRoot = sum over all c of Best[c][1]
withRoot = 1 + sum over all c of min(Best[c][0], Best[c][1])
return (withoutRoot, withRoot)
The running time of this algorithm is easily seen to be (n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.