# 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 = (a1b1c1) ∧ (a2b2c2) ∧ … ∧ (akbkck).

For each clause (aibici) 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 (aibici) 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!

Tags:
• #### Marathon (Part the First)

On race day, I got up at 3:30 a.m. I was in Evanston and needed to be at the starting line at McCormick Place before six, and I didn't have a car. I…

• #### Marathon logistics

On a brighter note, the marathon is tomorrow morning, and I went down to McCormick Place to get my Marathon Packet, which consists of a bib number…

• #### I feel like all my journal entries lately have been of epic length

...and yet there's all this stuff that I haven't been covering. I barely wrote about graduation, and I didn't say much about iD training or the…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic