Caminho simples no dag com bordas para trás

Qual é a complexidade do seguinte problema ( P? NP-hard?): $\in$

Entrada: um gráfico acíclico direcionado , um conjunto de arestas e dois nós distintos e . $D=(V,E)$ $E'\subset V\times V$ $s$ $t$

Pergunta: Seja denotar o gráfico formado adicionando a as arestas de . Existe um caminho simples de para em que usa pelo menos uma borda para trás? $G=(V,E\cup E')$ $D$ $E'$ $s$ $t$ $G$

Nota: 0) Um caminho simples é um caminho no qual nenhum vértice é repetido. Uma aresta traseira é uma aresta que contradiz a ordem parcial implícita no DAG. 1) o problema é fácil se solicitarmos o caminho simples para usar exatamente uma aresta inversa (ou um número constante) por redução trivial ao problema do caminho separado, que admite uma solução simples do PTime nos DAGs ( Perl e Shiloach, JACM'78 ) 2) o problema do caminho separado é NP-completo em gráficos gerais ( Fortune et al., TCS'80 ).

graph-algorithms time-complexity disjoint-paths Joseph Stack
fonte

e_{1}, . . ., e_{m}

$e_1,...,e_m$

E

$E$

s

$s$

t

$t$

G_{i} = (V, E^{'} \cup ⋃_{j = 1}^{i} {e_{j}})

$G_i = (V, E' \cup \bigcup_{j=1}^i \{ e_j \} )$

i = 1, 2, . . ., m

$i = 1,2,...,m$

E

$E$

G^{'} = (V, E^{'})

$G' = (V, E')$

s

$s$

t

$t$

E

$E$

E^{'}

$E'$

E^{'}

$E'$

O que é muito irritante para o seu problema é que o seguinte problema relacionado é facilmente considerado difícil para o NP: dado um gráfico e dois pares de vértices (s, t), (s ', t'), para determinar se há desmonte do vértice caminhos de s para te de s 'para t', mesmo quando t = s ', e mesmo em gráficos que são a união de dois DAGs. Ainda assim, isso não parece ajudar na pergunta que você faz.

a3nm

O problema de caminhos disjuntos é W [1] - difícil mesmo nos DAGs, e é um dever de casa mostrar que é NP-Duro nos DAGs. O algoritmo Shiloach é para o problema de dois caminhos disjuntos e, de maneira semelhante, funciona para o problema de caminhos disjuntos em DAGs, mas leva tempo n ^ k. Mas pelo menos admite um algoritmo XP para o seu problema.

Saeed