Vertex Cover Problem

The problem, simply

You get a graph: rooms are dots and hallways are lines. A camera in a room watches every hallway that touches that room. Choose the fewest rooms for cameras so that every hallway is watched. That set of rooms is a minimum vertex cover.

Give back the smallest number of cameras. Below, k stands for that answer.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every set of rooms.

1. For every number mask from 0 to 2^V - 1, put a camera in room i if bit i is on.
2. Skip sets that are not smaller than the best so far.
3. Check every hallway. If each one has a camera at one end, this set is the new best.

class VertexCoverBrute {
    public static int minCover(int n, int[][] edges) {
        int best = n;
        for (int mask = 0; mask < (1 << n); mask++) {  // bit i on: camera in room i
            int size = Integer.bitCount(mask);
            if (size >= best) continue;                // cannot beat the best
            boolean ok = true;
            for (int[] e : edges) {
                if ((mask >> e[0] & 1) == 0 && (mask >> e[1] & 1) == 0) { ok = false; break; }
            }
            if (ok) best = size;
        }
        return best;
    }
}

How long it takes: 2^V sets, each checked against E hallways, O(2^V * E). Extra room: O(V) at most. With 40 rooms this is already a trillion sets, even if the answer is just 5 cameras.

Way 2: the clever way

Use the guard's rule. Any dark hallway u-v forces a camera in u or in v. That gives a choice tree with only 2 branches per camera. With a budget of k cameras the tree has at most 2^k leaves, no matter how many rooms there are. This is backtracking where the work depends on the answer size k, not on V.

1. Try budgets k = 0, 1, 2, ... in order.
2. To test a budget: find a dark hallway. If there is none, the budget works. If the budget is 0, it fails.
3. Otherwise put a camera on one end and test budget k - 1. If that fails, move the camera to the other end and test again.
4. The first budget that works is the answer.

class VertexCoverBranch {
    public static int minCover(int n, int[][] edges) {
        boolean[] cam = new boolean[n];
        for (int k = 0; k <= n; k++) {                 // try budgets 0, 1, 2, ...
            if (canCover(edges, k, cam)) return k;
        }
        return n;
    }

    // can at most k more cameras watch every hallway?
    static boolean canCover(int[][] edges, int k, boolean[] cam) {
        int[] open = null;
        for (int[] e : edges) {
            if (!cam[e[0]] && !cam[e[1]]) { open = e; break; }   // first dark hallway
        }
        if (open == null) return true;                 // everything is watched
        if (k == 0) return false;                      // no cameras left
        for (int room : open) {                        // one of its two ends must get a camera
            cam[room] = true;
            boolean ok = canCover(edges, k - 1, cam);
            cam[room] = false;
            if (ok) return true;
        }
        return false;
    }
}

How long it takes: one budget test has at most 2^k leaves, and each step scans the hallways, O(2^k * E). Trying budgets 0, 1, ..., k adds them up to about twice the last one, so still O(2^k * E). When the answer is small, this is far faster than trying all 2^V sets. Extra room: the camera marks and the recursion depth k, O(V + k).

Another way: a fast guess that is at most double

When the museum is huge and you only need a good answer, not the best: walk the hallways, and whenever one is dark, put cameras at both ends. The dark hallways you picked never share a room, and the best answer needs a different camera for each of them, so this guess is at most twice the best. It runs in O(V + E). On the example it picks 0-1 and 3-4 and returns 4, size 4. On a line of 7 rooms it returns 6 while the best is 3, so the factor of 2 is real.

class VertexCoverApprox {
    public static Set<Integer> approxCover(int n, int[][] edges) {
        boolean[] cam = new boolean[n];
        Set<Integer> cover = new TreeSet<>();
        for (int[] e : edges) {
            if (!cam[e[0]] && !cam[e[1]]) {            // dark hallway: take both ends
                cam[e[0]] = cam[e[1]] = true;
                cover.add(e[0]);
                cover.add(e[1]);
            }
        }
        return cover;
    }
}

Watch out for

• Greedy by "most hallways first" sounds smart but is not exact either, and it can be even worse than double on special graphs.
• A room with a hallway to itself must get a camera. The branching code handles it, because both ends are the same room.
• Rooms with no hallways never need a camera.
• Remember to take the camera back after a failed branch, or later branches see wrong marks.

What interviewers ask next

• The graph is a tree. Use dynamic programming: for each room, the best cover of its subtree with and without a camera in it. A room without a camera forces cameras in all its children. O(V).
• The graph is bipartite. König's theorem: the minimum cover equals the maximum matching, which a matching algorithm finds in polynomial time.
• How is this related to the biggest set of rooms with no hallway between them? They are partners: the rooms without cameras form an independent set, so max independent set = V - min cover.
• Can you prune the branching more? If a room has more than k hallways, it must get a camera (otherwise you would need more than k neighbors). Rooms with one hallway can always take the camera on the other end. These kernel rules shrink the graph before branching.

Remember this

Grown-up words: rooms are vertices, hallways are edges, the camera set is a vertex cover, the budget search is a bounded search tree (a fixed parameter algorithm), the take-both-ends guess is the matching based 2-approximation, and NP-hard means no known fast exact method for all graphs.