En un gráfico, un conjunto independiente es un subconjunto de vértices que no contiene un borde como un subgráfico inducido. El problema de encontrar conjuntos independientes más grandes en un gráfico es una pregunta algorítmica fundamental, y difícil de resolver. Consideremos la cuestión más general de encontrar (el tamaño de) un conjunto libre de H más grande en un gráfico, donde libre de H significa que no induce un subgráfico que contiene una copia del gráfico fijo H como un subgráfico inducido.
Para el gráfico fijo H, dado el gráfico de entrada G, ¿es NP-difícil determinar el tamaño de un conjunto libre de H más grande en G?
¿Hay alguna manera sensata de construir una "tabla" de gráficos H (o clases de H), para completar las entradas con respuestas correctas de sí o "no" a la pregunta anterior? (Supongamos que "no" = P, e incluso que una entrada "no" significa que hay un algoritmo polytime para generar un conjunto libre de H más grande).
De lo contrario, ¿hay clases no triviales de H para las cuales la respuesta es sí? ... ¿No?
Estaba cavando, buscando dos preguntas sobre números cromáticos generalizados / libres de H --- aquí y aquí --- cuando se me ocurrió que el problema (aparentemente más simple) "dual" de un análogo de número de independencia libre de H También podría estar abierto. Conozco trabajos clásicos sobre un problema relacionado con gráficos aleatorios, cf. por ejemplo, Erdos, Suen y Winkler (1995) o Bollobas y Thomason (2000), que se encuentran en una línea de investigación aún muy activa. Entonces, tal vez ya haya algo de trabajo que aún no he visto para abordar esta pregunta más básica y que no se descubrió una búsqueda aproximada en Internet (de ahí la etiqueta de solicitud de referencia).
Respuestas:
[1] John M. Lewis, Mihalis Yannakakis: El problema de eliminación de nodos para propiedades hereditarias es NP-completo. J. Comput. Syst. Sci. 20 (2): 219-230 (1980)
fuente