Last problem on the 2006 foundations qual:
Let a "funny graph" be a finite directed-graph where each vertex is either "square" or "circular" (but not both), and each edge is between a square vertex and a circular vertex (in either order). Prove that the following problem is NP-complete.
- Given a funny graph, is there a way to color the circular vertices red or green, so that every square vertex either has an out-edge to a green vertex, or an in-edge from a red vertex.
My proof:
Let FGCOLOR = {〈G〉| G is a funny graph that is colorable so that every square vertex either has an out-edge to a green vertex or an in-edge from a red vertex }. We give a polynomial time reduction from 3SAT to FGCOLOR.
The reduction maps a Boolean formula φ to a graph G. Let φ be a formula with k clauses such as
&phi = (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (ak ∨ bk ∨ ck).
For each clause (ai ∨ bi ∨ ci) in φ, let there be a square vertex s in G such that
- ai is true if s has an out-edge to a green vertex;
- bi is true if s has an in-edge from a red vertex;
- ci is true if s has both.
Then all clauses (ai ∨ bi ∨ ci) in φ will be true iff all square vertices in G satisfy the definition of FGCOLOR. Therefore we can model 3SAT as an FGCOLOR problem. But 3SAT is NP-complete, therefore FGCOLOR must not be solvable in polynomial time. Therefore FGCOLOR is NP-complete.
Ideally, I think I should be more explicit about proving both directions of that iff. But I also think my construction works, and I thought of it all by myself! (My first idea was to reduce from the 3-coloring problem, but that didn't work for me. Which goes to show that you should always reduce from 3SAT. Always.)
I guess this might not be so special, really. But I'm excited, because it's been over four years since I've tried to do an NP-completeness proof. And I can do it! I can do it!