Em um gráfico, um conjunto independente é um subconjunto de vértices que não contém uma aresta como um subgrafo induzido. O problema de encontrar os maiores conjuntos independentes em um gráfico é uma questão algorítmica fundamental e difícil. Vamos considerar a questão mais geral de encontrar (o tamanho de) o maior conjunto livre de H em um gráfico, onde livre de H significa que ele não induz um subgrafo que contém uma cópia do gráfico fixo H como um subgrafo induzido.
Para o gráfico fixo H, dado o gráfico de entrada G, é NP difícil determinar o tamanho de um maior conjunto sem H em G?
Existe uma maneira sensata de construir uma "tabela" dos gráficos H (ou classes de H), de modo a preencher as entradas com respostas corretas sim ou "não" à pergunta acima? (Vamos fingir que "no" = P, e mesmo que uma entrada "no" signifique que existe um algoritmo polytime para gerar um maior conjunto sem H).
Na falta disso, existem classes não triviais de H para as quais a resposta é sim? ... não?
Eu estava pesquisando, analisando duas perguntas sobre números cromáticos generalizados / livres de H --- aqui e aqui --- quando me ocorreu que o problema (ostensivamente mais simples) "dual" de um número análogo de independência sem H também pode estar aberto. Estou ciente de artigos clássicos sobre um problema relacionado para gráficos aleatórios, cf. por exemplo, Erdos, Suen e Winkler (1995) ou Bollobas e Thomason (2000), que estão em uma linha de pesquisa ainda muito ativa. Portanto, talvez já exista algum trabalho que ainda não vi abordando essa questão mais básica e que uma pesquisa aproximada na Internet não descobriu (daí a tag de solicitação de referência).
Respostas:
[1] John M. Lewis, Mihalis Yannakakis: o problema de exclusão de nós para propriedades hereditárias é NP-completo. J. Comput. Syst. Sci. 20 (2): 219-230 (1980)
fonte