tag:blogger.com,1999:blog-3722233.post323026088387965615..comments2020-04-07T00:40:33.821-04:00Comments on Computational Complexity: Is there a NICE gadget for showing PLANAR HC is NPC?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-23249634044583223342012-01-06T13:51:57.243-05:002012-01-06T13:51:57.243-05:00A quick observation. In the simplest formulation t...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73135024091057160562012-01-06T12:27:50.387-05:002012-01-06T12:27:50.387-05:00Is CSProf as annoying in real life?
Anonymous 3:4...Is CSProf as annoying in real life?<br /><br />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.<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50631807978197921852012-01-06T10:41:45.803-05:002012-01-06T10:41:45.803-05:00As context, you might point out that the original ...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.David Johnsonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44734185366901057442012-01-06T10:18:52.766-05:002012-01-06T10:18:52.766-05:003-COL is the problem of, given a graph, is it 3 co...3-COL is the problem of, given a graph, is it 3 colorable.<br />Is is NPC. The link I gave is to a proof that<br />PLANAR 3-COL is NPC- given a planar graph,is it 3-colorable. That proof used a simple gadget<br />(at least simple to verify- looks hard to come up with)<br />and I was hoping for a similar-in-spirit gadget for planar HAM CYCLE (or HAM PATH or DIRECTED...)<br /><br />Given the comments both here and on CS Theory Stack Exchange<br />I am wondering if such a gadget is impossible and<br />also how one could formalize that statement and then proof it. <br /><br />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.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56958730311014173002012-01-06T03:26:30.684-05:002012-01-06T03:26:30.684-05:00The argument by anonymous (3:46pm) seems to miss s...The argument by anonymous (3:46pm) seems to miss some possibilities even when adding a single vertex.<br /><br />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).<br />I hope everyone sees how to extend this to several edge crossings.<br /><br />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/PATHAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91457752426728841432012-01-05T21:42:17.123-05:002012-01-05T21:42:17.123-05:00The argument by Anonymous 3:46 only shows that the...The argument by Anonymous 3:46 only shows that there is no way to remove crossings by adding a single vertex.<br /><br />What is 3-COL?<br />Ts nt hrd t wrt whl wrds, nd mks thngs sr t rd!CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11461311697687135602012-01-05T16:46:26.718-05:002012-01-05T16:46:26.718-05:00Assume there is an edge from A to B which cannot b...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71041339906991347522012-01-05T13:32:45.327-05:002012-01-05T13:32:45.327-05:00What is known about converting a non-planar graph ...What is known about converting a non-planar graph to a planar graph in general?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43735378819092999022012-01-03T19:44:01.156-05:002012-01-03T19:44:01.156-05:00That semester's web site has CLRS chapters pos...That semester's web site has CLRS chapters posted too. Under SOPA could that get the entire CMU domain blocked?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62812321763975531722012-01-03T18:26:02.643-05:002012-01-03T18:26:02.643-05:00It is Dexter Kozen's notes. They are published...It is Dexter Kozen's notes. They are published in book form now - "The design and analysis of algorithms"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89227167580796075032012-01-03T16:01:58.011-05:002012-01-03T16:01:58.011-05:00Instructors were Gary Miller and Danny Sleator tha...Instructors were Gary Miller and Danny Sleator that term.Anonymousnoreply@blogger.com