Partition sans H

Ceci est une question inspirée par le problème de la coupe H sans . Étant donné un graphe, une partition de son ensemble de sommets en parties est sans si n'induit pas une copie de pour tout , $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$ .

Je souhaite examiner la question suivante:

Quel est le moins pour lequel il existe une partition sans dans $r$ $H$ $r$ parties ?

Notez que lorsque est un seul bord, cela revient à trouver le nombre chromatique et est déjà NP-complet. Je me demande s'il est plus facile de montrer NP-complétude pour tout fixe pour ce problème (plus facile, par rapport à le montrer pour une coupe sans ). J'ai même pensé que cela pourrait être évident, mais je n'ai rien obtenu. Il est tout à fait possible que je manque quelque chose de très simple, et si tel est le cas, j'apprécierais quelques conseils! $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
la source

Vous voulez dire: pour tout

et pour tout

, le sous-graphe de

induit par

n'est pas isomorphe à

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Jukka Suomela

Je pense que la réponse de RJK à l'autre problème lié à cela s'applique à ce problème (en fait mieux qu'à l'autre problème).

Tsuyoshi Ito

@Jukka: Tout à fait, je le fais. Merci pour le pointeur, et pardonnez-moi d'être trop paresseux (au moins pour l'instant) pour mettre à jour la question en conséquence!

Neeldhara

@Tsuyoshi: Oui, et maintenant j'ai aussi une version plus élaborée de la réponse! Cependant, je dois dire que j'ai posté cela parce que je me suis retrouvé dans la situation "Je frappe un barrage routier en pensant à X et Y-semble-un-lié-et-plus facile". Je pensais juste que je devrais partager les détails de Y pour les autres qui pensaient à X, et ce n'était pas principalement destiné à être une demande de référence :)

Neeldhara

Serge Gaspers a fait référence à un vieux papier (1980) de Lewis et Yannakakis qui semble très pertinent ici!

RJK

Réponses:

Les premières références que je connais à ce type de problème sont les suivantes. Celles-ci sont également mentionnées dans l'article de Cowen, Goddard et Jesurum que j'ai mentionné dans l'autre fil.

Andrews et Jacobson. (1985) Sur une généralisation du nombre chromatique. Dans Proc. 16e Conférence internationale du Sud-Est sur la combinatoire, la théorie des graphes et l'informatique (Boca Raton 1985), Congr. Numer. 47 33–48.

Cowen, Cowen et Woodall. (1986) Colorations défectueuses des graphiques dans les surfaces: Partitions en sous-graphiques de valence bornée. J. Graph Theory 10 187–195.

Harary. (1985) Colorabilité conditionnelle dans les graphiques. Dans Graphs and Applications (Boulder 1982), Wiley – Interscience, pp. 127–136.

Harary et Jones (née Fraughnaugh). (1985) Colorabilité conditionnelle II: variations bipartites. Dans Proc. Conférence de Sundance sur la combinatoire et les sujets connexes (Sundance 1985), Congr. Numer. 50 205-218.

AFAIK, il n'y a pas encore de document donnant la dichotomie explicite P / NP-c pour divers choix de H. Cela a été fait, cependant, par Hell et Nesetril, pour un autre type de généralisation du nombre chromatique, "H-colorings ", aux homomorphismes.

RJK
la source

Merci beaucoup pour votre réponse très détaillée - très appréciée. C'est un ajout substantiel à ma liste de lecture, cela devrait me tenir occupé pendant un certain temps!

Neeldhara

Eh bien, ce n'est pas un problème, bien que, comme je l'ai mentionné précédemment, en plus du document JGT, il soit assez difficile de les retrouver. (En fait, je dois admettre que je n'ai pas encore beaucoup réussi, malgré le fait d'avoir eu accès à de nombreuses bibliothèques universitaires canadiennes.) En tout cas, le papier Cowen, Goddard et Jesurum est probablement le plus pertinent et répond à votre question / Moron pour H étant une étoile fixe, même limitée aux graphes planaires. Les classes ouvertes (je pense?) Les plus agréables de H à enfoncer seraient probablement des cycles ou des cliques.

RJK

Dans «Le partitionnement des sommets en propriétés héréditaires additives fixes est NP-difficile», Alastair Farrugia prouve que si $F_1$ et $F_2$ sont deux familles de graphes connectés, alors le problème du partitionnement d'un graphe en deux parties dont l'une est $F_1$ -gratuit et l'autre $F_2$ -free est NP-hard, sauf lorsque les deux $F_1$ et $F_2$ se composent du seul bord.

(Sans F = {pour tous les H en F, sans H})

Voir www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf

Aravind
la source