Cat Vs. Dog
Updated for clarity 23 Sep 2013.
A friend of mine recently pointed me to Spotify's Cat vs. Dog puzzle. The question is long, and so i'll summarize it without its motivating context.
You are given n votes, each of which is a pair of strings of the form (Ci, Dj) (a cat-lover vote) or (Dj, Ci) (a dog-lover) for some integers 1 ≤ i, j ≤ n. This collection of votes can contain repeats. Two votes (a, b) and (c, d) are said to conflict if a = d or b = c. So a conflict can only occur between a cat-lover vote and a dog-lover vote. Your job is to find the size of a maximal subcollection of the votes in which no two votes conflict.
Algorithm 1
Brute-force. Run through all possible subcollections of votes and test each for conflicts. Choose the biggest non-conflicting subcollection.
This procedure would take O(2n) time in the worst case, because there are 2n subcollections to check. That's very slow. Can we be more clever?
Algorithm 2
Yes, model the problem with a graph.
- Distinguish the votes by tagging each with a unique identifier, such as an integer between 1 and n. This takes O(n) time.
- Build the following undirected graph G. Make each vote a vertex, and add the edge {u, v} if u and v are conflicting votes. This takes O(n2) time. Notice that G is bipartite, because every edge connects a cat-lover vote to a dog-lover vote and no vertex is both a cat-lover vote and a dog-lover vote.
- Notice that every maximal subset of nonconflicting votes is the complement of a minimum vertex cover for G. So find the size k of a minimum vertex cover for G and return n − k. Now, finding the size of a minimum vertex cover in an arbitrary undirected graph is an NP-complete problem, and there's no known sub-exponential time way to do that. However, our graph is bipartite, and so by Koenig's theorem, the size of a minimum vertex cover of G equals the size of a maximum matching for G, the latter of which can be found by the Hopcroft-Karp algorithm in O(|E|√(n)) time, where |E| is the number of edges in G. In the worst case, |E| = n2 and running Hopcroft-Karp takes O(n2.5) time.
So all up, Algorithm 2 takes O(n2.5) time in the worst case.
Why no comments? Public comments take too much time to moderate and maintain, time better spent playing outside, but you can still email me private comments by clicking the 'Comment' link above.