Problema do caminho mais longo

Em teoria dos grafos e ciência da computação teórica, o problema do caminho mais longo é encontrar um caminho simples de comprimento máximo num dado grafo. Um caminho é chamado simples se não tem nenhum vértice repetido; O comprimento de um caminho pode ser medido tanto pelo seu número de arestas, ou (em grafos ponderados) pela soma dos pesos das suas bordas. Em contraste com o problema do caminho mais curto, que pode ser resolvido em tempo polinomial em gráficos sem ciclos de peso negativo, o problema do caminho mais longo é NP-difícil, o que significa que ele não pode ser resolvido em tempo polinomial para grafos arbitrários a menos que P = NP. Fortes resultados difíceis são também conhecidos por mostrar que é difícil aproximar. No entanto, ele tem uma solução em tempo linear para grafos acíclicos direcionados, que tem importantes aplicações em encontrar o caminho crítico em problemas de agendamento.

NP-dificuldade

A NP-dificuldade do problema do caminho mais longo sem peso pode ser demonstrado por meio de uma redução do problema do caminho Hamiltoniano: um grafo G tem um caminho hamiltoniano se e somente se o seu caminho mais longo tem um comprimento n - 1, onde n é o número de vértices em G. Em razão do fato de que o problema caminho hamiltoniano é NP-completo, esta redução mostra que a versão de decisão do problema do caminho mais longo é também NP-completo. Na decisão, a entrada deste problema é um grafo G e um número k; a saída desejada é "sim" se G contém um caminho de k ou mais arestas, e não de outra maneira.^[1]

Se o problema do caminho mais longo pode ser resolvido em tempo polinomial, que pode ser utilizado para resolver este problema de decisão, por descoberta de um caminho mais longo e, em seguida, comparando a sua extensão para o número k. Portanto, o problema do caminho mais longo é NP-difícil. Não é NP-completo, uma vez que não é um problema de decisão. ^[2]

Em grafos completos com pesos das arestas não-negativos, o problema do caminho mais longo com peso é o mesmo que o problema do caminho do caixeiro viajante, porque o caminho mais longo sempre inclui todos os vértices.^[3]

Gráficos acíclicos e caminhos críticos

Um caminho mais longo entre dois vértices dado s e t em um grafo ponderado G é a mesma coisa que um caminho mais curto em um gráfico -G derivada de G, alterando todo o peso de sua negação. Portanto, se os caminhos mais curtos podem ser encontrados em -G, em seguida, caminhos mais longos podem também ser encontrados em G.^[4]

Para a maioria dos gráficos, esta transformação não é útil porque cria ciclos de comprimento negativo em -G. Mas, se G é um gráfico acíclico dirigido, então ciclos negativos não podem ser criados, e um caminho mais longo em G pode ser encontrado no tempo linear através da aplicação de um algoritmo de tempo linear para os caminhos mais curtos em -G, que também é um gráfico acíclico dirigido.^[4] Por exemplo, para cada vértice v em um determinado DAG, o comprimento do caminho mais longo terminando em v pode ser obtido pelos seguintes passos:

1. Encontre uma ordenação topológica do dado DAG.
2. Para cada vértice v do DAG, na ordenação topológica, calcular o comprimento do caminho mais longo terminando em v, olhando para os seus vizinhos de entrada e adicionando um ao comprimento máximo gravado para os vizinhos. Se v não tem vizinhos de entrada, definir o comprimento do caminho mais longo terminando no v para zero. Em ambos os casos, registrar este número para que passos posteriores do algoritmo possa acessá-lo.

Uma vez que isto tenha sido feito, o caminho mais longo em todo o DAG pode ser obtido começando pelo vértice v com o valor maior registrado, então repetidamente andando para trás para a sua vizinha de entrada com o maior valor registrado, e invertendo a sequência de vértices encontrados desta maneira.

O método do caminho crítico para programar um conjunto de atividades envolve a construção de um gráfico acíclico dirigido em que os vértices representam marcos do projeto e as arestas representam as atividades que devem ser executadas após um marco e antes de outro; cada aresta é ponderada por uma estimativa de quantidade de tempo que a atividade correspondente levará para ser concluída. Em tal gráfico, o caminho mais longo a partir do primeiro marco para o último é o caminho crítico, que descreve o tempo total para a conclusão do projeto.^[4]

Caminhos mais longos de gráficos acíclicos dirigidos também podem ser aplicados no desenho gráfico em camadas: atribuir cada vértice v de um gráfico acíclico dirigido G para a camada cujo número é o comprimento do caminho mais longo terminando em resultados v numa atribuição de camada para G com o mínimo número possível de camadas.^[5]

Aproximação

Björklund, Husfeldt & Khanna (2004) escrevem que o problema do caminho mais longo em gráficos sem direções não ponderadas "é notório para a dificuldade de entender a sua difícil aproximação". ^[6] O melhor algoritmo de aproximação de tempo polinomial conhecido para este caso alcança apenas uma relação de aproximação muito fraca, ${\displaystyle n/\exp(\Omega ({\sqrt {\log n}}))}$.^[7] Para todo${\displaystyle \epsilon >0}$, não é possível aproximar o caminho mais longo para dentro de um fator de ${\displaystyle 2^{(\log n)^{1-\epsilon }}}$ a menos que NP esteja contido dentro de quasi-tempo polinomial determinístico; no entanto, há uma grande diferença entre este resultado contável e os algoritmos de aproximação conhecidos para este problema.^[8]

No caso de gráficos não ponderados, mas dirigidos, fortes resultados contáveis são conhecidos. Para cada ${\displaystyle \epsilon >0}$ o problema não pode ser aproximado dentro de um fator de ${\displaystyle n^{1-\epsilon }}$ a menos que P = NP, e com pressupostas complexidade teórica mais fortes que não pode ser aproximado dentro de um fator de ${\displaystyle n/\log ^{2+\epsilon }n}$.^[6] A técnica de codificação de cor pode ser usada para encontrar caminhos de comprimentos logarítmicos, se é que existem, mas o que dá uma relação de aproximação de apenas ${\displaystyle O(n/\log n)}$.^[9]

Complexidade parametrizada

O problema do caminho mais longo é parâmetro-fixo tratável quando parametrizado pelo comprimento do caminho. Por exemplo, ele pode ser resolvido no tempo linear no tamanho do grafo de entrada (mas exponencial do comprimento do percurso), por um algoritmo que realiza as seguintes etapas:

1. Realize uma busca em profundidade do grafo. Seja ${\displaystyle d}$ a profundidade da árvore de busca em profundidade resultante.
2. Use a sequência de caminho raiz-a-folha da árvore de busca em profundidade, na ordem em que foram atravessados pela pesquisa, para a construção de uma decomposição do caminho do gráfico, com largura de caminho ${\displaystyle d}$.
3. Aplicar programação dinâmica a esta decomposição de caminho para encontrar um caminho mais longo no tempo ${\displaystyle O(d!2^{d}n)}$, onde ${\displaystyle n}$ é o número de vértices do grafo.

Uma vez que a passagem de saída tem um comprimento pelo menos tão grande como ${\displaystyle d}$, o tempo de execução também é delimitada por ${\displaystyle O(\ell !2^{\ell }n)}$, onde ${\displaystyle \ell }$ é o comprimento do caminho mais longo.^[10] Utilizando um código de cores, a dependência do comprimento do percurso pode ser reduzida para exponencial isoladamente.^{[9][11][12][13]} A técnica de programação dinâmica similar mostra que o problema do caminho mais longo também é parâmetro – fixo tratável quando parametrizado pelo terceiro caminho do grafo.

Para os grafos de largura camarilha limitada, o caminho mais longo também pode ser resolvido através de um algoritmo de programação dinâmica em tempo polinomial. No entanto, o expoente do polinômio depende da camarilha de largura do grafo, por isso este algoritmo não é parâmetro – fixo tratável. O problema do caminho mais longo, parametrizado por camarilha de largura, é difícil para a classe de complexidade parametrizada ${\displaystyle W[1]}$ mostrando que um algoritmo de parâmetro – fixo tratável é improvável de existir.^[14]

Classes especiais de grafos

O problema do caminho mais longo pode ser resolvido em tempo polinomial sobre os complementos de grafos de comparabilidade.^[15] Ele também pode ser resolvido em tempo polinomial em qualquer classe de grafos com três larguras limitadas ou de largura pequena associação limitada, tais como os grafos de distância hereditária. No entanto, é NP-difícil, mesmo quando restrito a dividir gráficos, gráficos de círculo  ou grafos planares.^[16]

Referências

1. Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, ISBN 9783540443896, Algorithms and Combinatorics, 24, Springer, p. 114 .
2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction To Algorithms, ISBN 9780262032933 2nd ed. , MIT Press, p. 978 .
3. Lawler, Eugene L. (2001), Combinatorial Optimization: Networks and Matroids, ISBN 9780486414539, Courier Dover Publications, p. 64 .
4. Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms, ISBN 9780321573513 4th ed. , Addison-Wesley Professional, pp. 661–666 .
5. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), «Layered Drawings of Digraphs», Graph Drawing: Algorithms for the Visualization of Graphs, ISBN 978-0-13-301615-4, Prentice Hall, pp. 265–302 .
6. Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev (2004), «Approximating longest directed paths and cycles», Proc. Int. Coll. Automata, Languages and Programming (ICALP 2004), Lecture Notes in Computer Science, 3142, Berlin: Springer-Verlag, pp. 222–233, MR 2160935 .
7. Gabow, Harold N.; Nie, Shuxin (2008), «Finding long paths, cycles and circuits», International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 5369, Berlin: Springer, pp. 752–763, MR 2539968, doi:10.1007/978-3-540-92182-0_66 . For earlier work with even weaker approximation bounds, see Gabow, Harold N. (2007), «Finding paths and cycles of superpolylogarithmic length» (PDF), SIAM Journal on Computing, 36 (6): 1648–1671, MR 2299418, doi:10.1137/S0097539704445366  and Björklund, Andreas; Husfeldt, Thore (2003), «Finding a path of superlogarithmic length», SIAM Journal on Computing, 32 (6): 1395–1402, MR 2034242, doi:10.1137/S0097539702416761 .
8. Karger, David; Motwani, Rajeev; Ramkumar, G. D. S. (1997), «On approximating the longest path in a graph», Algorithmica, 18 (1): 82–98, MR 1432030, doi:10.1007/BF02523689 .
9. Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), «Color-coding», Journal of the ACM, 42 (4): 844–856, MR 1411787, doi:10.1145/210332.210337 .
10. Bodlaender, Hans L. (1993), «On linear time minor tests with depth-first search», Journal of Algorithms, 14 (1): 1–23, MR 1199244, doi:10.1006/jagm.1993.1001 . For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see Monien, B. (1985), «How to find long paths efficiently», Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud., 109, Amsterdam: North-Holland, pp. 239–254, MR 808004, doi:10.1016/S0304-0208(08)73110-4 .
11. Chen, Jianer; Lu, Songjian; Sze, Sing-Hoi; Zhang, Fenghui (2007), «Improved algorithms for path, matching, and packing problems», Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07) (PDF), pp. 298–307 .
12. Koutis, Ioannis (2008), «Faster algebraic algorithms for path and packing problems», International Colloquium on Automata, Languages and Programming (PDF), Lecture Notes in Computer Science, 5125, Berlin: Springer, pp. 575–586, MR 2500302, doi:10.1007/978-3-540-70575-8_47 .
13. Williams, Ryan (2009), «Finding paths of length k in O*(2^k) time», Information Processing Letters, 109 (6): 315–318, MR 2493730, arXiv:0807.3026, doi:10.1016/j.ipl.2008.11.004 .
14. Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2009), «Clique-width: on the price of generality», Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09) (PDF), pp. 825–834, consultado em 30 de novembro de 2015, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 .
15. Ioannidou, Kyriaki; Nikolopoulos, Stavros D. (2011), «The longest path problem is polynomial on cocomparability graphs» (PDF), Algorithmica, doi:10.1007/s00453-011-9583-5 . For earlier work on more restrictive subclasses of co-comparability graphs, see Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D. (2011), «The longest path problem has a polynomial solution on interval graphs» (PDF), Algorithmica, 61 (2): 320–341, MR 2822187, doi:10.1007/s00453-010-9411-3  and Uehara, Ryuhei; Valiente, Gabriel (2007), «Linear structure of bipartite permutation graphs and the longest path problem», Information Processing Letters, 103 (2): 71–77, MR 2322071, doi:10.1016/j.ipl.2007.02.010 .
16. Ioannidou, Mertzios & Nikolopoulos (2011).

Ligação externa

• "Find the Longest Path", música de Dan Barrett