¿Max-Cut APX-complete en gráficos sin triángulo?

9

En el problema de Max-Cut , se busca un subconjunto S de vértices de un gráfico simple no dirigido dado de modo que el número de aristas entre S y el complemento de S sea lo más grande posible.

Max-Cut es APX-complete en gráficos de grado acotado [PY91], y de hecho APX-complete en gráficos cúbicos (es decir, gráficos de grado 3) [AK00].

Max-Cut es NP-completo en gráficos de grado sin triángulo como máximo 3 [LY80] (sin triángulo significa que el gráfico de entrada no contiene K_3, el gráfico completo en 3 vértices, como un subgrafo).

Pregunta: ¿Max-Cut APX-complete en gráficos sin triángulo? (Nota: grados arbitrarios permitidos)

Gracias.

ACTUALIZACIÓN: Se ha encontrado una respuesta, pero aún estaría interesado en una referencia para este resultado, si es que hay alguna.

Referencias

[AK00] P. Alimonti y V. Kann: Algunos resultados de completitud APX para gráficos cúbicos. Theor Comput Sci. 237 (1-2): 123-134, 2000. doi: 10.1016 / S0304-3975 (98) 00158-3

[LY80] JM Lewis y M. Yannakakis: El problema de eliminación de nodos para propiedades hereditarias es NP-completo. J. Comput. Syst. Sci. 20 (2): 219-230, 1980. doi: 10.1016 / 0022-0000 (80) 90060-4

[PY91] CH Papadimitriou y M. Yannakakis: Optimización, aproximación y clases de complejidad, J. Comput. System Sci., 43 (3): 425-440, 1991. doi: 10.1016 / 0022-0000 (91) 90023-X

Standa Zivny
fuente
Si no encuentra una referencia, y parece que este es un argumento original, considere publicarlo aquí: meta.cstheory.stackexchange.com/questions/784/…
Suresh Venkat

Respuestas:

14

Sí, mediante una reducción de MaxCut a MaxCut sin triángulo. Esto es lo que Wikipedia llama una reducción de L

GGGGG

Colin McQuillan
fuente
99
Gracias Colin! Mientras buscaba una respuesta, descubrí el mismo truco que usted llama "3 estiramientos", también conocido como 2 subdivisiones. Por lo que he encontrado, probablemente apareció por primera vez en este artículo: Svatopluk Poljak: Una nota sobre conjuntos estables y coloración de gráficos, Comentario. Matemáticas. Univ. Carolinae 15 (1974) 307-309 (disponible aquí: dml.cz/handle/10338.dmlcz/105554 )
Standa Zivny