Quiero un gadget fácil de probar Planar Hamiltonian Cycle NP-Complete (de Hamiltonian Cycle)

Se sabe que el ciclo hamiltoniano (jamón para abreviar) tiene NP completo y que el ciclo de jamón planar tiene NP completo. La prueba para Planar Ham Cycle no es de Ham Cycle.

¿Hay un buen dispositivo que, dado un gráfico G, reemplazará todos los cruces con algún dispositivo plano para que tenga un gráfico plano G 'tal que

G tiene un ciclo de jamón si G 'tiene un ciclo de jamón.

(Estaré contento con variantes, como Ham Path o Ham Cycle dirigido o Directed Ham Path).

cc.complexity-theory np-hardness planar-graphs hamiltonian-paths Bill GASARCH
fuente

Una observación algo trivial. Suponga que incrusta

y los bordes

cruzan, con

aparecen en sentido horario alrededor del punto de cruce. Reemplácelo por un dispositivo

que tenga cuatro puntos de entrada

correspondientes a

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

x, v, y, u

$x,v,y,u$

P_{x v y u}

$P_{xvyu}$

x^{'}, v^{'}, y^{'}, u^{'}

$x',v',y',u'$

. Si un ciclo hamiltoniano en

usa ambas aristas

entonces en

el ciclo correspondiente tendría que autocruzarse. Por supuesto, esto supone que la interpretación más ingenua de lo que es un `` Gadget" es y también que el ciclo de Hamilton en

tiene que seguir los mismos bordes como el ciclo correspondiente de

x, v, y, u

$x,v,y,u$

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

G^{'}

$G'$

G^{'}

$G'$

G

$G$

Marek Chrobak

¿Qué es el ciclo del jamón? No asuma que todos entienden sus abreviaturas.

Tsuyoshi Ito

@MarekChrobak: Estoy de acuerdo con tu comentario. Da dos formas de escapar de su argumento. Creo que el más natural es el segundo: hay un ciclo hamiltoniano

si existe un ciclo hamiltoniano

x \to y \to \dots \to u \to v \to \dots \to x

$x\to y\to\dotsb\to u\to v\to\dotsb\to x$

G

$G$

x \to x^{'} \to \dots \to u^{'} \to u \to \dots \to y \to y^{'} \to \dots \to v^{'} \to v \to \dots \to x

$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

@ Tsuyoshi: Significa ciclo hamiltoniano. Creo que es razonable suponer que todos pueden resolverlo.

domotorp

@Bill: Me pregunto por qué crees que debería existir un dispositivo así. El número de cruces al incrustar un gráfico arbitrario en el plano puede ser muy grande (

para el gráfico completo; vea el lema del cruce). Entonces, si comienzas con una gráfica con

aristas y muchas aristas (por ejemplo, casi cuadrática), entonces la gráfica incrustada con los cruces agregados como vértices tiene una estructura completamente diferente ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Respuestas:

No. Al menos, no hay un dispositivo "agradable" para un crossover.

Sea y una cruz que queremos reemplazar. $(a, b)$ $(x,y)$ ingrese la descripción de la imagen aquí

Hay muchos casos para nuestro gráfico, , pero tenemos que satisfacer al menos los siguientes cuatro. Caso 1: hay al menos un ciclo hamiltoniano, pero ninguno usa ninguno de los bordes. Caso 2: hay al menos un ciclo, y todos los ciclos usan exactamente uno de los dos bordes. Caso 3: hay al menos un ciclo, y todos los ciclos usan ambos bordes. Caso 4: no hay ciclo hamiltoniano. $G$

Si nuestro dispositivo tiene dos (o más) vértices para cada uno de adyacentes a todos los mismos vecinos (de modo que y retengan los vecinos de a), entonces no será necesariamente plano. Para satisfacer el primero de nuestros casos anteriores, no podemos tener vértices nuevos en el gadget. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Para satisfacer el caso 3 anterior, debemos tener al menos dos bordes en el gadget. Ni el par plano y de cobertura, ni satisfacen el caso 2, por lo que necesitamos un tercer borde. Sin pérdida de generalidad, que esos tres sean . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

Sin embargo, ese reemplazo rompe el cuarto caso, porque podría contener un ciclo hamiltoniano cuando no lo hace. Tomemos, por ejemplo, donde y $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ . no es plano y no tiene un ciclo hamiltoniano. $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$ ingrese la descripción de la imagen aquí

$G' = (V, E')$ $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'$ $a, q, x, t, p, s, b, y, r, a$

$(b, y)$ $(a, x)$ $G'$

$(a, b), (a, y), (x, b)$

Dado que agregar tres bordes rompe el caso 4, agregar más no ayudará.

$a, b, x$ $y$

(Nota: ¡avíseme si cometí algún error arriba!)

( ~~Nota 2: tuve algunas buenas figuras, pero no puedo publicarlas.~~ Publicado).

Kyle
fuente

Creo que deberías poder publicar cifras ahora.

Jukka Suomela