Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper

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: quals
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded