Imagine a graph of Facebook friends, where users are vertexes and friendships are edges.
Write a function named findMinimumVertexCover that accepts three parameters:
a reference to a BasicGraph,
a string representing the name of a vertex to start from,
and an integer K.
Your function should return a set of strings representing names of vertexes identifying a minimum vertex cover.
A vertex cover is a subset of an undirected graph's vertexes such that each and every edge in the graph is incident to at least one vertex in the subset.
A minimum vertex cover is a vertex cover of the smallest possible size.
For example, in the graph below, all of the following would be vertex covers:
{"A", "C", "D", "E", "F"}; {"A", "B", "D"}; {"B", "D"}; {"A", "B"}.
Each one is a vertex cover because each edge touches at least one vertex in the cover.
The last two vertex covers, {"B", "D"} and {"A", "B"}, are minimum vertex covers, because there is no vertex cover with fewer vertexes.
A-----B-----C
| /|\
| / | \
D__/ E \__F
Understand that because the graph is undirected, that means for every edge that leads from some vertex v1 to v2, there will be an edge that leads from v2 to v1.
If there are two or more minimum vertex covers, then you can return any one of them.
Think of this as a backtracking problem.
The implementation of this function should consider every possible vertex subset, keeping track of the smallest one that covers the entire graph.
Try all possible vertex combinations using a "choose-explore-unchoose" pattern and keep track of state along the way.
You may assume that the parameter values passed are valid.
