Tuesday, January 03, 2012

Is there a NICE gadget for showing PLANAR HC is NPC?

(I have already posted this question on CS Theory Stack Exchange.)

If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget that removes crossings (see here for some lecture notes on it. They are not mine. The original link is here but I can't figure out the real author, though it is likely whoever taught Algorithms at CMU in Spring of 2004.)

Lets say we know that HAM CYCLE is NPC (we do!). Is there a gadget to remove crossings so you can show that PLANAR HAM CYCLE is NPC? The problem of PLANAR HAM CYCLE is NPC so there sort-of has to be a gadget; but is there a NICE one? (The proof that PLANAR HAM Cycle is NPC is from SAT and I find it rather complicated (see here for the original paper.) I have tried to extract an uncrossing gadget from it but have not been able to it.

SO- I ask you, do you know of a NICE gadget for removing crossings in a graph so that we can easily go from HAM CYCLE NPC to PLANAR HAM CYCLE NPC.



  1. Instructors were Gary Miller and Danny Sleator that term.

  2. It is Dexter Kozen's notes. They are published in book form now - "The design and analysis of algorithms"

  3. That semester's web site has CLRS chapters posted too. Under SOPA could that get the entire CMU domain blocked?

  4. What is known about converting a non-planar graph to a planar graph in general?

  5. Assume there is an edge from A to B which cannot be drawn without crossing other edges. If there were a way to add a new vertex C so that an edge could be drawn from A to C without crossing other edges, and an edge could be drawn from C to B without crossing other edges then you could just remove C and draw the line. So, a non-planar graph cannot be converted to planar by simply adding new vertices to help in this way.

  6. The argument by Anonymous 3:46 only shows that there is no way to remove crossings by adding a single vertex.

    What is 3-COL?
    Ts nt hrd t wrt whl wrds, nd mks thngs sr t rd!

  7. The argument by anonymous (3:46pm) seems to miss some possibilities even when adding a single vertex.

    Suppose for a start we need only to accept one crossing for edge (u,v), and in our drawing it does cross edge (u',v'). We could easily add a vertex w exactly *at* the crossing, remove (u,v) and (u',v') and instead add the edges (x,w) (where x in {u, v, u', v'}), making the graph planar. In fact we don't even need to add a vertex, just removing (u,v) and adding (u,u') and (u',v).
    I hope everyone sees how to extend this to several edge crossings.

    Unfortunately such a construction doesn't help with HAM CYCLE/PATH. I'm afraid it might even be possible to show (way beyond my skills) that no such local substitutions exist that also preserve the (non)existence of a HAM CYCLE/PATH

  8. 3-COL is the problem of, given a graph, is it 3 colorable.
    Is is NPC. The link I gave is to a proof that
    PLANAR 3-COL is NPC- given a planar graph,is it 3-colorable. That proof used a simple gadget
    (at least simple to verify- looks hard to come up with)
    and I was hoping for a similar-in-spirit gadget for planar HAM CYCLE (or HAM PATH or DIRECTED...)

    Given the comments both here and on CS Theory Stack Exchange
    I am wondering if such a gadget is impossible and
    also how one could formalize that statement and then proof it.

    A Gadget would give a linear time (perhaps also log space) reduction from from HAM CYCLE to PLANAR HAM CYCLE. I wonder if YOU can show there is no such reduction. I know that I cannot.

  9. As context, you might point out that the original proof of the NP-hardness of planar Hamiltonian Circuit was via a transformation from 3SAT (Garey, Johnson, & Tarjan, SICOMP 5 (1976),704-714). It had crossover components, but not the kind you are looking for. That paper cited a slightly earlier paper (Garey, Johnson, & Stockmeyer, TCS 1 (1976), 237-267) that included a proof that planar directed Hamiltonian PATH was NP-complete, this time by a transformation from EXACT COVER. For neither problem were we able to come up with a proof using a simple reduction from the corresponding Hamiltonian problem for general graphs, so the question you as is certainly interesting and (as far as I know) open.

  10. Is CSProf as annoying in real life?

    Anonymous 3:46 made a simple statement about one approach that would not work. A nice contribution to an otherwise empty discussion to that point. Perhaps an undergraduate of Bill's trying to participate. A noble post. No reason for CSProf to restate the conclusion in a dismissive way.

    3-COL is an abbreviation I've seen used many times before, so perhaps CSProf was covering his lack of familiarity and inability to do a simple web search on 3-COL NPC with arrogance and sarcasm.

  11. A quick observation. In the simplest formulation taking on the idea from the 3-coloring transformation, a crossing gadget (that transforms input non-planar graph HAM-CYCLE problem to a planar graph HAM-CYCLE problem) needs to ensure that a path entering the gadget has to leave the gadget at that specific vertex diametrically opposite to the entrance vertex (since in the non-planar graph we cannot have any turns in between two of its vertices). This was straightforward to encode in the 3-coloring gadget, could this also be done with paths?