logo CodeStepByStep logo

findMinimumVertexCover

Language/Type: C++ graphs collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

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 pointer to a Vertex to start from, and an integer K. Your function should return a set of vertex pointers 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.

Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.