Problemas de gráfico que são NP-completos em gráficos direcionados, mas polinomiais em gráficos não direcionados

16

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?

RB
fonte
2
st-connectivity é um exemplo interessante para classes de nível inferior análogas - L para o caso não direcionado versus NL-complete para o caso direcionado.
Huck Bennett

Respostas:

18

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 1t1 1s2t2

Bangye
fonte
11
Você poderia fornecer uma citação para este ser NPC?
Austin Buchanan
8
k2k
Muito bom @Bangye!
RB
10

NP

Mohammad Al-Turkistany
fonte
3

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.

Michael Lampis
fonte
1

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.

Suresh Venkat
fonte