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
Respuestas:
Sí, mediante una reducción de MaxCut a MaxCut sin triángulo. Esto es lo que Wikipedia llama una reducción de L
fuente