# 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*(2^{n}) time in the worst case, because there are 2^{n} 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*(*n*^{2}) 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*| =*n*^{2}and running Hopcroft-Karp takes*O*(*n*^{2.5}) time.

So all up, Algorithm 2 takes *O*(*n*^{2.5}) time in the worst case.