Classes de gráficos com ciclo hamiltoniano fácil, mas TSP NP-rígido

13

O Problema do Ciclo Hamiltoniano (HC) consiste em encontrar um ciclo que atravessa todos os vértices em um determinado gráfico não direcionado. O Travelling Salesman Problem (TSP) consiste em encontrar um ciclo que atravesse todos os vértices em um determinado gráfico ponderado pelas arestas e minimize a distância total medida pela soma dos pesos das arestas no ciclo. HC é um caso especial de TSP, e ambos são conhecidos por serem NP-completos [Garey & Johnson]. (Consulte os links acima para obter mais detalhes e variantes desses problemas.)

Existem classes de gráficos estudadas nas quais o Problema do Ciclo Hamiltoniano é solucionável em tempo polinomial por meio de um algoritmo não trivial , mas o Problema do Vendedor Viajante é difícil para NP?

Não trivial é excluir classes como a classe de gráficos completos, onde é garantido que existe um ciclo hamiltoniano e pode ser encontrado com facilidade, ou geralmente classes de gráficos em que é garantido que sempre existe um HC.

Standa Zivny
fonte

Respostas:

20

As cópias nem sempre são hamiltonianas, possuem testes de tempo polinomial para Hamiltonicidade e são difíceis de resolver o problema do vendedor ambulante.

De um modo mais geral, o problema do ciclo hamiltoniano pode ser resolvido em tempo polinomial (mas não é tracionável em parâmetro fixo) em gráficos de largura de clique limitada ; veja, por exemplo, Fomin et al., "Clique-largura: sobre o preço da generalidade", SODA'09. Mas, novamente, como essas famílias de gráficos incluem os gráficos completos, o TSP é duro com esses gráficos.

David Eppstein
fonte
Estou curioso sobre sua última declaração. Isso ocorre porque o tour pelo TSP identificaria efetivamente as panelinhas, fazendo com que todos os vértices de clique fossem contíguos no tour?
precisa saber é o seguinte
1
Não, quero dizer simplesmente que o TSP é difícil, mesmo em um gráfico completo, e gráficos completos estão entre os gráficos com largura de clique limitada. Os gráficos completos em si não fornecem uma boa resposta para a pergunta porque a Hamiltonicidade é trivial para eles, mas as superclasses das panelinhas (como as cografias) podem ter testes de Hamiltonicidade não triviais, mas polinomiais.
David Eppstein
11

Que tal gráficos completos ? Como o TSP sempre pode ser reduzido a uma instância em gráficos completos (adicionando distâncias adequadas entre não arestas), ainda é difícil para o NP resolver o TSP em gráficos completos. Mas qualquer gráfico completo é hamiltoniano.

Hsien-Chih Chang 張顯 之
fonte
Sim, claro, obrigado! Esqueceu-se de excluir gráficos completos e, nesse caso, todas as classes de gráficos em que HC é solucionável trivialmente.
Standa Zivny
3
@Standa Zivny: Não tenho certeza se você deseja editar a pergunta ou não, mas se você deseja excluir "todas as classes de gráficos em que o HC é trivialmente solucionável", você deve editar a pergunta. No entanto, duvido que seja possível formular a distinção entre o caso em que o HC pode ser resolvido "facilmente" e o caso em que o HC pode ser resolvido "trivialmente".
Tsuyoshi Ito
@ Tsuyoshi Ito: Um bom ponto, eu editei a pergunta.
Standa Zivny
@StandaZivny - Nem todos os gráficos triviais para HC são difíceis para TSP, por exemplo, gráficos de caminho.
RB
3

Existem muitas classes infinitas de gráficos que são conhecidos por possuir circuitos hamiltonianos. Duas classes especialmente interessantes são os n-cubos e os gráficos de Halin. Uma maneira de pensar nos gráficos de Halin é incorporar uma árvore com pelo menos 3 vértices e que não tenha vértices de valência dois no plano e depois passar um circuito simples pelos vértices 1 valentes da árvore.

http://en.wikipedia.org/wiki/Halin_graph

Sabe-se que esses gráficos têm um HC e, na verdade, são pancíclicos (circuitos de todos os comprimentos) ou não possuem exatamente um comprimento de circuito que deve ter comprimento uniforme.

Joseph Malkevitch
fonte