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⟩|Gis 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 from3SATtoFGCOLOR.The reduction maps a Boolean formula φ to a graph

G. Let φ be a formula withkclauses such as&phi = (

a_{1}∨b_{1}∨c_{1}) ∧ (a_{2}∨b_{2}∨c_{2}) ∧ … ∧ (a_{k}∨b_{k}∨c_{k}).For each clause (

a_{i}∨b_{i}∨c_{i}) in φ, let there be a square vertexsinGsuch that

a_{i}is true ifshas an out-edge to a green vertex;b_{i}is true ifshas an in-edge from a red vertex;c_{i}is true ifshas both.Then all clauses (

a_{i}∨b_{i}∨c_{i}) in φ will be true iff all square vertices inGsatisfy the definition ofFGCOLOR. Therefore we can model3SATas anFGCOLORproblem. But3SATis NP-complete, thereforeFGCOLORmust not be solvable in polynomial time. ThereforeFGCOLORis 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!