Encontrar um sub-torneio acíclico máximo, dado dois sub-torneios acíclicos

Dado um torneio , onde e ser dois acíclico sub-torneio de .S 1 S 2$T$$S_1$$S_2$$T$

O seguinte problema é NP-Complete: Localizando um sub-torneio acíclico máximo , que é um subconjunto de ?S 1 ∪ S $S$$S_1 \cup S_2$

O problema em questão pode ser resolvido em tempo polinomial? Caso contrário, indique a NP-Completeness.

Mantendo como tal e removendo apenas os vértices de , um torneio acíclico máximo de pertencente a pode ser obtido em tempo polinomial. A solução assim obtido pode não ser o mesmo que o máximo sub-acíclico competiam .S 2 S ′ S 1 ∪ S 2 S ′$S_1$$S_2$$S'$$S_1 \cup S_2$$S'$$S$

O algoritmo de tempo polinomial é baseado na etapa de compactação no algoritmo de compactação iterativo para o vértice de feedback definido no torneio a partir do artigo

Resultados de rastreabilidade de parâmetros fixos para problemas de feedback em torneios , Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

Se encontrar um sub-torneio acíclico máximo for NP-completo, não tenho outra opção, exceto encontrar S ' , então gostaria de saber se encontrar S é NP-completo ou não.$S$$S'$$S$

considere a redução da cobertura do vértice para o problema acima.

considere o gráfico com o vértice V = {1,2, .. n}$G(V,E)$

Seja T o torneio com vértices para o vértice i = 1,2 ... n$x_{i},y_{i},z_{i}$

construa o torneio com arestas na ordem de .se existir uma aresta (i, j), então z j , x i . x i , y i pertence a T 1 para i = 1,2, ... n e z i pertence T $x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}...x_{n},y_{n},z_{n}$$z_{j},x_{i}$$x_{i},y_{i}$$T_{1}$$z_{i}$$T_{2}$para i = 1,2 ... n. É claro que e T 2 são acíclico.$T_{1}$$T_{2}$

Exemplo para a construção

considere o gráfico G (V, E) com o conjunto de vértices {1,2,3} e as arestas com a construção (1,2) (2,3) da seguinte maneira

O torneio tem vértices com construção da seguinte forma$x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$

O passo 1 direcionou as arestas para todos os vértices.$x_{1}$

direcionou arestas para todos os vértices, exceto x $y_{1}$$x_{1}$

direcionou arestas para todos os vértices, exceto x 1 , y $z_{1}$$x_{1},y_{1}$

direcionou arestas para todos os vértices, exceto x 1 , y 1 , z $x_{1}$$x_{1},y_{1},z_{1}$

e repita o processo até que todas as bordas do torneio sejam construídas

passo 2: (1,2) tem uma aresta, então troque a direção da aresta de para ( y 2 , x 1 ) da mesma forma para (1,3) reivindicação: G tem uma cobertura de vértice de tamanho k apenas se T tiver um conjunto de vértices de tamanho k$(x_{1},y_{2})$$(y_{2},x_{1})$

um caso é claro, se G tem uma cobertura de vértice de tamanho k, então certamente T tem um valor de fvs de tamanho k

$i<j$$x_{i},z_{j}$$y_{i},z_{i},x_{k},y_{k},z_{k},x_{j},y_{j}$$i<k<j$$x_{i},z_{j}$

por favor, veja e verifique.