Problemas polinomiais em classes de grafos definidas por subgráficos cíclicos induzidos proibidos

Cruzado do MO .

Seja $C$ uma classe de gráfico definida por um número finito de subgráficos induzidos proibidos, todos cíclicos (contêm pelo menos um ciclo).

Existem problemas de gráfico NP-rígido que podem ser resolvidos em tempo polinomial para $C$ diferente da capa Clique e Clique?

Se bem me lembro, isso é impossível para um conjunto independente (a menos que $P=NP$ ).

A pesquisa em graphclasses.org não encontrou nenhuma.

Uma classe para a qual Clique e Capa são polinomiais é C5, C6, X164, X165, sunlet4, sem triângulo

Editar

Negativo para IS e Dominação está neste documento . Na página 2, os gráficos $S_{i,j,k}$ .

Eu acho que existem vários problemas difíceis que se tornam fáceis para gráficos sem triângulo; especialmente aqueles que lidam diretamente com triângulos como Partição em triângulos (G tem uma partição em triângulos?). Outros exemplos menos triviais incluem:

• Problema de corte estável (G tem um conjunto independente S de modo que GS seja desconectado?). Veja: Sobre sutsets estáveis ​​nos gráficos, Matemática Aplicada Discreta. 105 (2000) 39-50.

• Base do gráfico de interseção (G é o gráfico de interseção dos subconjuntos de um conjunto de terra do elemento k?). Veja: Problema [GT59] em: Garey & Johnson, Computadores e Intratabilidade: Um Guia para a Teoria da Completude NP.

Aqui estão alguns exemplos adicionais para a resposta de Mon Tag:

• O problema do corte desconectado ( admite um conjunto de vértices S de tal modo que G - S e o subgrafo de G induzido por S são desconectados) é NP-completo (veja aqui ). É fácil ver que esse problema é polinomialmente solucionável para gráficos sem triângulo (daí também o problema do Stable Cutset, como mencionado por Mon Tag).$G$$S$$G-S$$G$$S$

• O reconhecimento de gráficos de linhas triangulares é NP-completo (veja aqui ). Também é fácil ver que esse problema se torna polinomialmente para gráficos de entrada sem triângulo.

• É difícil calcular a correspondência máxima conectada (veja aqui . Uma correspondência é conectada se, para qualquer par de arestas correspondentes, houver outra aresta do gráfico incidente em ambos). Pode ser provado que este problema pode ser resolvido é polinomialmente para gráficos -free.$(C_3, C_4, C_5)$

$(K_s,I_t)\text{-free}$$(K_s,K_{1,t})\text{-free}$

$K_{1,t}$

Depois de pensar um pouco sobre isso, parece fácil provar o seguinte (original?):

$\{H_1,...H_k\}$$H_i$$\mathcal{C}$$(H_1,...,H_k)\text{-free}$

$(H_1,...,H_k)\text{-free}$$H_i$$G_1,G_2$$r$$H_i$$(u,v)$$G_1,G_2$$l = \lceil r/3 \rceil$$l$$(u,p_1,p_2,...,p_l,v)$$G'_1, G'_2$$(H_1,...,H_k)\text{-free}$$3\lceil r/3 \rceil + 3 > r$$G_1,G_2$

$G_1$$(H_1,...,H_k)\text{-free}$$G'_1$$H_i$$r=15$$G_1$$l = 5$

Também podemos estender o resultado negativo ao problema do NPC do ciclo hamiltoniano, na verdade é um corolário imediato ao seguinte (original?):

$k \geq 3$$G$$\leq k$

$G$$v$$outdeg(v) + indeg(v) \leq 3$$G$$G'$$v$$indeg(v )=1$$v$$indeg(v)=2$$G'$$\geq k$$G''$$G$

Corolário: os problemas do ciclo e do caminho hamiltoniano permanecem NP-completos, mesmo se restritos aos , nos quais cada contém um ciclo.H $(H_1,...,H_k)\text{-free}$$H_i$

MAX-CUT permanece NP-completo.

O corte máximo simples do lema 3.2 é NP-completo nas duas classes de gráficos a seguir:

gráficos que não contêm ciclos de comprimento no máximo , para cada .k ≥ $k$$k \ge 3$

Eles estão subdividindo uma aresta duas vezes.

De "MAX-CUT e relações de contenção em gráficos, Marcin Kaminski"