Como provar encontrar dois caminhos que são pelo menos k arestas além é NP-difícil?

Question

Deixe $G=(V, E)$ ser um não, não, e ligado gráfico.Dadas duas iniciar vértices $s_1$ e $s_2$ e de final de dois vértices $t_1$ e $t_2$ existe um caminho a partir de $s_1$ para $t_1$ e $s_2$ para $t_2$ de tal forma que o mais próximo número de arestas entre os dois caminhos é, no mínimo, $k$?Dois caminhos $k$ fechar se o mínimo de menor distância entre qualquer vértice no primeiro caminho para qualquer vértice na segunda caminho é $k$.

Eu estava pensando em redução de 3SAT e deixar o primeiro caminho representar as variáveis e o segundo caminho representar as cláusulas, mas eu não tenho certeza para onde ir a partir daí.

Answer 1

Você pode reduzir de 3SAT.

O gráfico tem duas partes.Uma parte é a "variável" parte.Para cada uma das variáveis $v_1,\ldots,v_n$ há dois, três vértices $v_i^+,v_i^-,v_i$, e esta parte é composta dos seguintes bordas, para $i \in [n]$:

$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$

Aqui $v_0$ é um novo vértice, identificado com $s_1$, e $v_n$ é identificado com $t_1$.

A segunda parte é a "cláusula" parte.Para cada uma das cláusulas $C_1,\ldots,C_m$ há quatro vértices $w_j^1,w_j^2,w_j^3,w_j$, ligado tanto quanto antes, com $s_2$ e $t_2$.

Nós ligar $v_i^b$ com $w_j^r$ através de um caminho de comprimento $k$ (para alguns, grande o suficiente constante $k$) se o literal $v_i^b$ (quer $v_i$ ou $\overline{v_i}$, de acordo com $b$) é o oposto de $j$'th literal em $C_j$.

Também, nós tomamos todas as mindpoints um desses caminhos, e conectar todos eles, tornando-os em uma panelinha).

Podemos pensar em uma $(s_1,t_1)$-caminho como uma verdade de atribuição, e de um $(s_2,t_2)$-o caminho de como identificar uma satisfeito literal em cada cláusula.A distância mínima é mais do que $k$ se este é realmente o caso, e apenas $k$ caso contrário.

Verifique, também, que não há nenhum ponto para os caminhos do cruzamento entre as partes.Se apenas um dos caminhos cruzes, em seguida, os dois caminhos serão juntos (em algum distância constante, que para grande o suficiente $k$ vai ser menor do que $k$ imediatamente após o cruzamento.Se ambos cruz, então o ponto médio panelinha vai garantir que eles são a uma distância de, no máximo, 1.