I have to write a code such that it returns the size of the subset which contains a set of vertices such that each edge has at least one of its two ends points in this set. This is called a vertex cover, and my code has to return the minimum vertex cover.
Input: the root of the graph (that is not going to be cyclic) Output: the size of the smallest vertex cover.
For this, my vCover calls the vCoverHelper method and passes in the root of the graph, the one dimensional array that I will use to store the minimum vertex cover for that particular node, and i (which is initially set to zero) which indexes the one dimensional array. This is what the helper method looks like:
private int vCoverHelper(DirectedGraphNode root, int[] memo, int i) {
if (memo[i] != 0) {
return memo[i];
}
if (root.getOutDegree() == 0) {
memo[i] = 1;
return 1;
}
else{
List<DirectedGraphNode> children = root.getOutgoingNodes();
int numChild = root.getOutDegree();
while(numChild != 0) {
if(i != 0){
int x = 1 + vCoverHelper((DirectedGraphNode) children.get(numChild - 1), memo, i - 1)
+ children.get(numChild - 1).getOutDegree();
int y = vCoverHelper((DirectedGraphNode) children.get(numChild - 1), memo, i - 1)
+ root.getOutDegree();
memo[i] = Math.min(x, y);
numChild--;
}
}
}
return memo[i];
}
Basically what I am trying to do is there are two possible for the minimum vertex cover for a particular node. The first case is that the current node is included in the vertex cover and then look at its grandchildren and include them in the vertex cover, or the current node is not included in the vertex cover and we include it's children in the vertex cover.
My code returns the wrong answer and I think the reason for that is it is not storing the current minimum vertex cover in the array memo correctly. I think there is a problem especially with indexing i. It is not correctly updating i. How can I fix this code?
The reason I need the memo array is that after this, I want to be able to write a separate method which uses the memo array and recovers the subset.
Basically what I am trying to do is there are two possible for the minimum vertex cover for a particular node. The first case is that the current node is included in the vertex cover and then look at its grandchildren and include them in the vertex cover, or the current node is not included in the vertex cover and we include it's children in the vertex cover.
Consider a tree like the following:
A
/|\
/ | \
B C D
/|\
/ | \
E F G
The unique minimum vertex cover for this tree is {A, C} — please take a moment to convince yourself of that — even though A is the parent of C. So your breakdown into two cases is not correct, unless you know much more about your input than you've decided to share.
If you know that your graph will be a tree — or what Wikipedia calls an arborescence ("a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v") — then for any given vertex, there are two cases:
You can find the minimum cover in linear time by computing two pieces of information for the subtree rooted at each vertex: the minimum size of any cover of that subtree (call it minCoverAny[i]), and the minimum size of any such cover that includes the vertex itself (call it minCoverWithRoot[i]). You can compute these in a single recursive pass over the tree:
Then, once you've populated those, you do a second recursive pass over the tree to find the actual vertices in the minimum cover.