Estou procurando problemas que são conhecidos por serem NPCs para gráficos direcionados, mas que possuem um algoritmo polinomial para gráficos não direcionados.
Vi a pergunta sobre o contrário aqui, problemas "direcionados" que são mais fáceis do que sua variante "não direcionada" , mas estou procurando por dureza no lado direcionado.
Por exemplo, o conjunto de arestas de feedback é conhecido por ser NPC em tempo direcionado, mas polinomial, solucionável em gráficos não direcionados.
Quais outros problemas naturais têm a mesma propriedade?
Respostas:
O primeiro problema que me vem à cabeça é o problema de 2 caminhos (ou mais geralmente o problema do caminho k). Dado e ( s 2 , t 2 ) , encontre dois caminhos separados de s 1 a t 1 e s 2 a t 2 , respectivamente. O problema é o NPC para gráficos direcionados, mas solucionável em tempo polinomial para gráficos não direcionados (embora não seja trivial).( s1 1, t1 1) ( s2, t2) s1 1 t1 1 s2 t2
fonte
fonte
No problema Path Coloring, recebemos uma árvore T e uma coleção de caminhos nessa árvore (a idéia é que T é uma rede de comunicação e os caminhos são solicitações de comunicação). Queremos colorir os caminhos com um número mínimo de cores, para que dois caminhos que compartilham uma borda tenham cores distintas.
Esse problema é conhecido por ser solucionável em tempo polinomial se T for uma árvore não direcionada de grau limitado. No entanto, é NP-completo se T é uma árvore binária bidirecional. Acredito que ambos os resultados são apresentados no artigo abaixo.
[1] T. Erlebach e K. Jansen. "A complexidade da coloração do caminho e agendamento de chamadas". Ciência da Computação Teórica, 255 (1-2): 33–50, 2001.
fonte
Se não me engano, obter uma aproximação constante de fator para a árvore Steiner é NP-difícil em gráficos direcionados, mas é tempo-P em gráficos não-direcionados.
fonte