Quero um gadget fácil para provar o Ciclo Hamiltoniano Planar NP-Completo (do Ciclo Hamiltoniano)

Sabe-se que o ciclo hamiltoniano (presunto abreviado) é NP-completo e que o ciclo planar de presunto é NP-completo. A prova para o Ciclo de Presunto Planar não é do Ciclo de Presunto.

Existe um gadget legal que, dado um gráfico G, substitua todos os cruzamentos por algum gadget planar, para que você tenha um gráfico planar G 'tal que

G tem um ciclo de presunto se G 'possui um ciclo de presunto.

(Ficarei feliz com as variantes, como caminho do presunto ou ciclo do presunto direcionado ou caminho do presunto direcionado.)

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

Uma observação um tanto trivial. Suponha que você incorpore

G

$G$ e as arestas

(x, y)

$(x,y)$ e

(u, v)

$(u,v)$ cruzem, com

x, v, y, u

$x,v,y,u$ aparecendo no sentido horário em torno do ponto de cruzamento. Substitua-o por um gadget

P_{x v y u}

$P_{xvyu}$ que possui quatro pontos de entrada

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

$x',v',y',u'$ correspondentes a

x, v, y, u

$x,v,y,u$ . Se um ciclo hamiltoniano em

G

$G$ usa ambas as arestas

(x, y)

$(x,y)$ e

(u, v)

$(u,v)$ então em

G^{'}

$G'$ o ciclo correspondente teria que se auto-atravessar. Isto, obviamente, pressupõe a interpretação mais ingênua do que um `` dispositivo" é e também que o ciclo hamiltoniano em

G^{'}

$G'$ necessidades de seguir as mesmas bordas como o ciclo correspondente no

G

$G$ .

Marek Chrobak

O que é o ciclo do presunto? Por favor, não assuma que todos entendem suas abreviações.

Tsuyoshi Ito

@MarekChrobak: Concordo com sua observação. Você dá duas maneiras de escapar do seu argumento. Eu acho que o mais natural é a segunda: Há um Hamiltonian ciclo

sse existe um 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. Eu acho que é razoável supor que todos possam descobrir isso.

Domotorp

@ Bill: Estou me perguntando por que você acha que esse gadget deveria existir. O número de cruzamentos ao incorporar um gráfico arbitrário no plano pode ser muito grande (

para o gráfico completo - consulte o lema do cruzamento). Então, se você começar com um grafo com

arestas e muitas arestas (digamos perto quadrática), em seguida, o gráfico incorporado com os cruzamentos adicionados como vértices tem uma estrutura completamente diferente ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Respostas:

Não. Pelo menos, nenhum gadget "legal" para um crossover.

Seja e uma cruz que queremos substituir. $(a, b)$ $(x,y)$ insira a descrição da imagem aqui

Existem muitos casos para o nosso gráfico, , mas temos que satisfazer pelo menos os quatro seguintes. Caso 1: existe pelo menos um ciclo hamiltoniano, mas nenhum utiliza uma das extremidades. Caso 2: existe pelo menos um ciclo e todos os ciclos usam exatamente uma das duas arestas. Caso 3: existe pelo menos um ciclo e todos os ciclos usam as duas arestas. Caso 4: não há ciclo hamiltoniano. $G$

Se o nosso dispositivo tem dois (ou mais) vértices de cada um de adjacente a todos os mesmos vizinhos (de modo a que e reter 's vizinhos), então não irá necessariamente ainda ser planar. Para satisfazer o primeiro dos nossos casos acima, não podemos ter novos vértices no gadget. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Para atender ao caso 3 acima, precisamos ter pelo menos duas arestas no gadget. Nenhum par planar e de cobertura, nem satisfaz o caso 2, por isso precisamos de uma terceira aresta. Sem perda de generalidade, sejam esses . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

No entanto, essa substituição quebra o quarto caso, porque poderia conter um ciclo hamiltoniano quando não. Tome, por exemplo, onde e $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ . não é plano e não possui um 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$ insira a descrição da imagem aqui

Então onde $G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ . é plano e possui um ciclo hamiltoniano ( $\{(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$

Observe que se a borda não foi adicionada em vez de , então não teria um ciclo hamiltoniano. Parece que você precisa conhecer o ciclo possível para escolher a aresta corretamente. $(b, y)$ $(a, x)$ $G'$

Existe um problema semelhante ao fazer com que o gadget inclua uma das arestas diagonais, como: . $(a, b), (a, y), (x, b)$

Como adicionar três arestas quebra o caso 4, adicionar mais não ajuda.

Portanto, nenhum gadget "legal" existe. Pode ser que exista um gadget que preste mais atenção aos vizinhos de cada de e , mas isso não parece muito "agradável". $a, b, x$ $y$

(Nota: informe-me se cometi algum erro acima!)

( ~~Nota 2: Tive alguns números interessantes, mas não consigo publicá-los.~~ Publicado.)

Kyle
fonte

Eu acho que você deve poder postar números agora.

Jukka Suomela