Encontrar un sub-torneo acíclico máximo dados dos sub-torneos acíclicos

Dado un torneo donde y haber dos acíclico sub-torneo de . $T$ $S_1$ $S_2$ $T$

¿Es NP-Complete el siguiente problema: Encontrar un sub-torneo acíclico máximo , que es un subconjunto de ? $S$ $S_1 \cup S_2$

¿Se puede resolver el problema dado en tiempo polinómico? De lo contrario, indique la integridad de NP.

Manteniendo como tal y eliminando solo los vértices de , se puede obtener un torneo acíclico máximo perteneciente a en tiempo polinómico. La solución de obtenida de este modo puede no ser el mismo que el máximo acíclico sub-torneo . $S_1$ $S_2$ $S'$ $S_1 \cup S_2$ $S'$ $S$

El algoritmo de tiempo polinómico se basa en el paso de compresión en el algoritmo de compresión iterativo para el vértice de retroalimentación establecido en el torneo desde el documento

Resultados de trazabilidad de parámetros fijos para problemas de retroalimentación en torneos , Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

Si encontrar un sub-torneo acíclico máximo es NP completo, entonces no tengo más remedio que encontrar , así que deseo saber si encontrar es NP completo o no. $S$ $S'$ $S$

ds.algorithms np-hardness graph-algorithms Prabu
fuente

posible duplicado de ENCONTRANDO UN SUB TORNEO ACÍCLICO MÁXIMO DADO DOS SUB TORNEOS ACÍCLICOS

Dave Clarke

Lo siento. Solo lea todos los comentarios por duplicado. Este es un reenvío válido. Ignora mi voto para cerrar.

Dave Clarke

¿Estás eliminando arcos o vértices de la unión? En otras palabras, ¿su problema es como conjunto de arco de retroalimentación o conjunto de vértice de retroalimentación? Su pregunta no está del todo clara y los dos tipos de problemas son bastante diferentes.

Warren Schudy

@Warren Es un problema de conjunto de vértices de retroalimentación. Primer problema Dado el sub-torneo acíclico T1 y T2 de T. El conjunto de vértices de retroalimentación debe pertenecer a T1 (se puede encontrar en tiempo polinómico), mientras que en el segundo problema, el conjunto de vértices de retroalimentación puede presentar tanto en T1 como en T2. Mi pregunta es si el segundo puede resolverse en tiempo polinómico

Prabu

¿Cuál es la diferencia entre S1 y s1?

Tsuyoshi Ito

Respuestas:

considere la reducción de la cobertura de vértices al problema anterior.

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

sea T el torneo con vértices para vértice i = 1,2 ... n $x_{i},y_{i},z_{i}$

construye el torneo con aristas en orden de si existe una arista (i, j) entonces . pertenece a para i = 1,2 ... ny pertenece a $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. Está claro que y son acíclicos. $T_{1}$ $T_{2}$

Ejemplo para la construccion

Considere el gráfico G (V, E) con el conjunto de vértices {1,2,3} y las aristas de construcción (1,2) (2,3) como sigue

El torneo tiene vértices con la construcción de la siguiente manera $x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$

El paso 1 ha dirigido aristas a todos los vértices. $x_{1}$

ha dirigido aristas a todos los vértices excepto $y_{1}$ $x_{1}$

ha dirigido aristas a todos los vértices excepto $z_{1}$ $x_{1},y_{1}$

tiene bordes dirigidos a todos los vértices excepto $x_{1}$ $x_{1},y_{1},z_{1}$

y repite el proceso hasta construir todos los bordes del torneo

paso 2: (1,2) tiene un borde, así que cambia la dirección del borde de a manera similar para (1,3) reclamo: G tiene una cubierta de vértice de tamaño k solamente si T tiene un conjunto de vértices de retroalimentación de tamaño k $(x_{1},y_{2})$ $(y_{2},x_{1})$

un caso es claro, si G tiene una cubierta de vértice de tamaño k, entonces seguramente T tiene un fvs de tamaño 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, ver y verificar.

Prabu
fuente

T

$T$

x_{i}

$x_i$

z_{j}

$z_j$