Problèmes polynomiaux dans les classes de graphes définis par des sous-graphes cycliques induits interdits

Crossposted de MO .

Soit une classe de graphes définie par un nombre fini de sous-graphes induits interdits, tous cycliques (contenant au moins un cycle).$C$

Existe-t-il des problèmes de graphes NP-difficiles qui peuvent être résolus en temps polynomial pour autre que Clique et Clique cover?$C$

Si je me souviens bien, cela est impossible pour un ensemble indépendant (sauf si ).$P=NP$

La recherche dans graphclasses.org n'en a pas trouvé.

Une classe pour laquelle Clique et Clique cover sont polynomiales est C5, C6, X164, X165, sunlet4, sans triangle

Éditer

Négatif pour IS et Domination est dans cet article . Page 2, les graphes .$S_{i,j,k}$

Je pense qu'il y a un certain nombre de problèmes difficiles qui deviennent faciles pour les graphiques sans triangle; en particulier ceux qui traitent directement des triangles tels que la partition en triangles (G a-t-il une partition en triangles?). D'autres exemples moins triviaux comprennent:

• Problème de coupe stable (G a-t-il un ensemble indépendant S tel que GS est déconnecté?). Voir: Sur les sutsets stables dans les graphiques, Discrete Applied Math. 105 (2000) 39-50.

• Base du graphe d'intersection (G est-il le graphe d'intersection de sous-ensembles d'un ensemble de sol à k éléments?). Voir: Problème [GT59] dans: Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.

Voici quelques exemples supplémentaires de la réponse de Mon Tag:

• $G$$S$$G-S$$G$$S$

• Reconnaître que les graphiques à lignes triangulaires sont NP-complets (voir ici ), Il est également facile de voir que ce problème devient polynomial pour les graphiques d'entrée sans triangle.

• $(C_3, C_4, C_5)$

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

$K_{1,t}$

Après y avoir réfléchi un peu, il semble facile de prouver ce qui suit (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$

Nous pouvons également étendre le résultat négatif au problème de NPC du cycle hamiltonien, en effet c'est un corollaire immédiat au suivant (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$

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

MAX-CUT reste NP-complet.

Le lemme 3.2 simple max-cut est NP-complet dans les deux classes de graphiques suivantes:

$k$$k \ge 3$

Ils subdivisent deux fois un bord.

Extrait de "MAX-CUT et relations de confinement dans les graphiques, Marcin Kaminski"