23

It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.

Is there a nice gadget that will, given a graph G, replace all of the crossings with some planar gadget so that you have a planar graph G' such that

G has a Ham cycle iff G' has a Ham cycle.

(I'll be happy with variants- like Ham path or directed Ham Cycle or Directed Ham Path.)

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Bill GASARCH
  • 549
  • 2
  • 4
  • 7
    A somewhat trivial observation. Suppose you embed $G$ and edges $(x,y)$ and $(u,v)$ cross, with $x,v,y,u$ appearing clockwise around the crossing point. Replace it by a gadget $P_{xvyu}$ that has four entrance points $x',v',y',u'$ corresponding to $x,v,y,u$. If a hamiltonian cycle in $G$ uses both edges $(x,y)$ and $(u,v)$ then in $G'$ the corresponding cycle would have to self-cross. This of course assumes the most naive interpretation of what a ``gadget" is and also that the hamiltonian cycle in $G'$ needs to follow the same edges as the corresponding cycle in $G$. – Marek Chrobak Jan 03 '12 at 20:13
  • 4
    What is Ham Cycle? Please do not assume everyone understands your abbreviations. – Tsuyoshi Ito Jan 04 '12 at 02:55
  • 2
    @MarekChrobak: I agree with your remark. You give two ways to escape your argument. I think the most natural one is the second one: There is a Hamiltonian Cycle $x\to y\to\dotsb\to u\to v\to\dotsb\to x$ in $G$ iff there exists a Hamiltonian Cycle $x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$. – Bruno Jan 04 '12 at 18:14
  • 12
    @Tsuyoshi: It means Hamiltonian cycle. I think it is reasonable to assume that everyone can figure it out. – domotorp Jan 05 '12 at 04:32
  • @MarekChrobak: (1) is P_{xvyu} a path that goes x-v-y-u ? (2) By Planar Ham Cycle I mean that the original graph is planar. Your solution might be helpful for the problem where you want the Ham Cycle itself to be planar (not cross itself), which is not my problem but is still interesting. – Bill GASARCH Jan 05 '12 at 15:13
  • @Bill: you say: "... Your solution might be helpful for the problem where you want the Ham Cycle itself to be planar ...": but if $G'$ is planar (as you asked), then every Ham Cycle on it must be planar, too; so the Marek's note seems correct to me ?!? – Marzio De Biasi Jan 05 '12 at 16:24
  • @Bruno: perhaps the (only) way you can achieve what you suggest, is to exand every edge of the original non-planar graph $G$ to a series of parallel edges that "carry" the information about the order of traversal of the edges $x \to x'$, $u \to u'$, $y \to y'$, $v'\to v$ of the planar gadget in $G'$ ... but I have no idea on how to do it :-) – Marzio De Biasi Jan 05 '12 at 16:35
  • 2
    @Bill, I merged your new ID with the previous one so you should be able to comment. (ps: if you want you can register your user account to keep using the same user even when you remove the cookies from your browser.) – Kaveh Jan 05 '12 at 22:13
  • 3
    @Bill: I am wondering why you think such a gadget should exist. The number of crossings when embedding an arbitrary graph into the plane can be very large ($\Theta(n^4)$ for the complete graph - see the crossing lemma). So, if you start with a graph with $n$ edges and many edges (say near quadratic) then the embedded graph with the crossings added as vertices has completely different structure... – Sariel Har-Peled Jan 08 '12 at 22:49
  • maybe we can show that for any embedding of an explicit hamiltonian graph, any gadget used to construct a planar graph would violate Grinberg's theorem. – didest Jan 11 '12 at 19:37

1 Answers1

13

No. At least, no "nice" gadget for one crossover.

Let $(a, b)$ and $(x,y)$ be a cross we want to replace.enter image description here

There are many cases for our graph, $G$, but we have to satisfy at least the following four. Case 1: there is at least one hamiltonian cycle, but none use either of the edges. Case 2: there is at least one cycle, and all cycles use exactly one of the two edges. Case 3: there is at least one cycle, and all cycles use both edges. Case 4: there is no hamiltonian cycle.

If our gadget has two (or more) vertices for each of $a, b, x, y$ adjacent to all the same neighbors (so that $a_0$ and $a_1$ retain $a$'s neighbors) then $G'$ will not necessarily still be planar. In order to satisfy the first of our cases above, we then cannot have any new vertices in the gadget.

In order to satisfy case 3 above, we must have at least two edges in the gadget. Neither planar and covering pair, $(a, x), (y, b)$ nor $(a, y), (x, b)$ satisfies case 2, so we need a third edge. Without loss of generality, let those three be $(a, y), (y, b), (x,b)$.

However, that replacement breaks the fourth case, because $G'$ could contain a hamiltonian cycle when $G$ does not. Take, for example, $G = (V, E)$ where $V = \{a, b, x, y, p, q, r, s, t\},$ and $E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$. $G$ is not planar and does not have a hamiltonian cycle.enter image description here

Then $G' = (V, E')$ where $E' = \{(a, y), (y, b), (x, b)\} \cup$ $\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$. $G'$ is planar, and has a hamiltonian cycle ($a, q, x, t, p, s, b, y, r, a$).

Note that if $(b, y)$ was the edge not added instead of $(a, x)$, then $G'$ would not have a hamiltonian cycle. It seems that you'd have to have knowledge of the possible cycle to choose the edge correctly, though.

A similar problem exists for having the gadget include one of the diagonal edges, such as: $(a, b), (a, y), (x, b)$.

Since adding three edges breaks case 4, adding more won't help.

Thus, no "nice" gadget exists. It could be that a gadget exists that pays more attention to the neighbors of each of $a, b, x$ and $y$, but that doesn't seem very "nice".

(Note: please let me know if I made any errors above!)

(Note 2: I had some nice figures, but can't post them. Posted.)

Kyle
  • 261
  • 1
  • 7