Cálculo de conjuntos sem H máx

11

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).

RJK
fonte
3
Se k e H forem ambos fixos, você poderá apenas enumerar todos os subconjuntos de vértices de tamanho k e verificar se eles contêm H como um subgrafo induzido. Este será um algoritmo de tempo polinomial.
Robin Kothari
desculpe pela bobagem: editando para remover todas as instâncias do k!
RJK

Respostas:

10

HHHH

[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)

Serge Gaspers
fonte
Spot on! Obrigado pela referência! Talvez esse tipo de abordagem também possa ser (foi?) Aplicada ao problema de partição?
RJK
1
Eu não sigo o raciocínio aqui. O problema é difícil de NP, mesmo quando H não possui arestas, desde que H tenha pelo menos dois vértices.
András Salamon
HH
Esta resposta (revisão 2) refere-se ao problema de encontrar o maior subgrafo induzido que não contém H como subgrafo . O resultado de Lewis e Yannakakis se aplica ao problema de encontrar o maior subgrafo induzido que não contém H como subgrafo induzido , mas a condição em H para que a propriedade seja não trivial é diferente.
Tsuyoshi Ito
HH