Considera este problema:
Dado un gráfico no dirigido , encuentre tal que:
- es un subgrafo inducido de
- no tiene 3 camarillas
- es máximo
Por lo tanto, se debe eliminar el menor número de vértices de para que se eliminen las 3 camarillas.
Un problema equivalente sería encontrar una coloración 2 para tal que si y ,
La diferencia (absoluta) entre el número de nodos con color 1 y el número de nodos con color 2 es máxima.
¿Alguien puede pensar en un algoritmo de tiempo polinómico para resolver uno de estos problemas?
algorithms
graph-theory
graphs
optimization
Alexandre
fuente
fuente
Respuestas:
Ambas definiciones dejan su problema NP-hard, y han sido respondidas en teoría.
La Interpretación 1, donde necesita el subgrafo libre de triángulos más grande, es NP-Hard y ha sido respondida aquí .
Aquí se ha respondido la interpretación 2, donde necesita una partición de modo que ambos sub-gráficos inducidos estén libres de triángulos .
Tenga en cuenta que las respuestas a las que he vinculado son para la ausencia general de y son una clase de Hard.H NP
fuente