Problème de coupe sans H

Supposons que l'on vous donne un graphe H. connecté, simple et non orienté

Le problème de coupe sans H est défini comme suit:

Étant donné un graphe simple et non orienté G, existe-t-il une coupure (partition des sommets en deux ensembles non vides, L, R) de sorte que les graphes induits par les ensembles de coupes (L et R) ne contiennent pas tous les deux un sous-graphe isomorphe à H .

Par exemple, lorsque H est le graphe avec deux sommets reliés par une seule arête, le problème est le même que pour déterminer si un graphe est biparti et est en P.

Dans le cas où H est un triangle, c'est comme la version vertex du problème du triangle monochromatique .

Je pense que j'ai pu montrer que lorsque H est 2-connecté avec au moins trois sommets, le problème de coupe sans H est NP-Complete.

Je n'ai pas pu trouver de références à ce problème (et donc, aucun résultat).

Pouvons-nous abandonner la condition de connectivité 2 et prouver la complétude de NP?

Quelqu'un connaît-il des résultats connus qui impliqueraient ce qui précède ou un résultat plus fort (ou pensez-vous que cela pourrait être pertinent)?

Vous pouvez rechercher le terme "bipartition" ou "partition de sommet" ou "coloration" plutôt que "couper". Diverses généralisations du nombre chromatique le long des lignes auxquelles vous faites allusion ont été envisagées depuis le milieu des années 80 (ou peut-être plus tôt). Il existe quelques premières références difficiles à trouver dans les conférences canadiennes sur la combinatoire, mais vous voudrez peut-être consulter Cowen, Goddard et Jesurum (JGT ou SODA 1997) et les références / citations connexes.

Modifié le 15/02/2011

Comme indiqué par Aravind et Moron (dans les commentaires ci-dessous), les références suivantes montrent que le problème de coupe sans est difficile à NP, sauf dans les cas triviaux.$H$

D. Achlioptas. La complexité de la colorabilité sans Mathématiques discrètes. 165/166 (1997) 21-30. [pdf] .$G$

A. Farrugia. La partition des sommets en propriétés héréditaires induites additives fixes est difficile à NP. Électron. J. Combin. 11 (2004) # R46 (9 pages).

Je me rends compte que cela pourrait ne pas répondre directement à votre question (sur les références), mais je voudrais esquisser une approche possible pour montrer la dureté NP sans la condition 2-connectés. Il y a deux choses qui manquent: l'une est une preuve de la dureté NP du `` problème source '', pour ainsi dire, et l'autre est que je me réduit à une version `` colorée '' de H-cut qui peut ou peut ne pas être utile. En ce qui concerne le premier goulot d'étranglement, je pense avoir une preuve dans mon esprit que je suis paresseux au sujet de la formalisation, j'espère donc que j'y arriverai bientôt. J'ai pensé à réduire la version colorée à celle que vous présentez, cependant, avec peu de chance jusqu'à présent. Je suis également très curieux de connaître votre preuve dans le cas où H est 2-connecté, pourriez-vous éventuellement fournir quelques détails?

La version colorée est donc la suivante: chaque sommet du graphe est équipé d'une liste de couleurs d'une palette P (un ensemble fixe et fini). Nous devons trouver une coupe pour qu'aucune partition n'induise une copie monochromatique de H, c'est-à-dire qu'il n'y ait pas de sous-ensemble de | H | les sommets qui induisent une copie de H et la liste de couleurs correspondante ont une intersection non vide.

Voici une réduction d'une variante restreinte de d-SAT, où d est | H |. (Notez que cela ne fonctionnerait évidemment pas lorsque d = 2).

La variante restreinte de d-SAT est la suivante:

1. Chaque clause n'a que des littéraux positifs ou négatifs, permettez-moi de faire référence à des clauses telles que les clauses P et N respectivement,

2. Chaque clause P peut être associée à une clause N de telle sorte que les deux clauses impliquent le même ensemble de variables.

(J'ai une idée de pourquoi cette version apparemment restreinte peut être difficile - une restriction très étroitement liée est difficile, et je peux imaginer une réduction à partir de là, bien que je puisse facilement me tromper!)

Compte tenu de ce problème, la réduction se suggère peut-être. Le graphique a un sommet pour chaque variable de la formule. Pour chaque clause C_i, induisez une copie de H sur l'ensemble des variables qui participent à la clause, et ajoutez la couleur i à cet ensemble de sommets. Ceci termine la construction.

Toute affectation correspond naturellement à une coupe:

L = ensemble de toutes les variables définies sur 0, R = ensemble de toutes les variables définies sur 1.

L'affirmation est qu'une affectation satisfaisante correspond à une coupe sans H monochrome.

En d'autres termes, (L, R), lorsqu'il est donné par une affectation satisfaisante, serait tel que ni L ni R n'induisent une copie monochromatique de H. Si L a une telle copie, alors notez que la clause P correspondante doit avoir eu toutes ses variables sont mises à 0, ce qui contredit le fait que l'affectation était satisfaisante. Inversement, si R a une telle copie, alors la clause N correspondante doit avoir eu toutes ses variables mises à 1, contradiction à nouveau.

Inversement, considérez n'importe quelle coupe et définissez les variables d'un côté sur 1 et de l'autre sur 0 (notez que peu importe la façon dont vous le faites - compte tenu du type de formule avec laquelle nous travaillons, d'une affectation et c'est inversé sont équivalentes en ce qui concerne la satisfiabilité). Si une clause n'est pas satisfaite par cette affectation, nous pouvons la retracer à une copie monochromatique de H sur l'un des côtés, en contradiction avec la transparence monchromatique H de la coupe.

La raison pour laquelle il faut se livrer à la coloration est que les copies de H peuvent interférer pour créer des copies erronées de H qui ne correspondent pas aux clauses, dans une tentative de réduction directe. En effet, il échoue - gravement - même lorsque H est quelque chose d'aussi simple qu'un chemin.

Je n'ai pas eu de chance de me débarrasser des couleurs, et je ne suis pas sûr d'avoir simplifié le problème. Cependant, j'espère que - si c'est correct - ce pourrait être un début.