Alex Raichev

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.

  1. Distinguish the votes by tagging each with a unique identifier, such as an integer between 1 and n. This takes O(n) time.
  2. 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.
  3. 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.

Author: Alex Raichev
Date: 2013-04-02
Tags: algorithm, puzzle