My rhymes are so phat.

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 = (a₁ ∨ b₁ ∨ c₁) ∧ (a₂ ∨ b₂ ∨ c₂) ∧ … ∧ (a_k ∨ b_k ∨ c_k).

For each clause (a_i ∨ b_i ∨ c_i) in φ, let there be a square vertex s in G such that

• a_i is true if s has an out-edge to a green vertex;
• b_i is true if s has an in-edge from a red vertex;
• c_i is true if s has both.

Then all clauses (a_i ∨ b_i ∨ c_i) 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!