H-freie Partition

Dies ist eine Frage, die vom Problem des H-freien Schnitts inspiriert ist . Bei einem Graph eine Partition der Artikulationssatz in Teile ist -freie wenn nicht eine Kopie induzieren für alle , . $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$

Ich möchte die folgende Frage prüfen:

Was ist das kleinste für das es eine freie Aufteilung in Teile gibt? $r$ $H$ $r$

Beachten Sie, dass wenn eine einzelne Kante ist, dies dem Finden der chromatischen Zahl gleichkommt und bereits NP-vollständig ist. Ich frage mich, ob es für dieses Problem einfacher ist, die NP-Vollständigkeit für ein festes zu zeigen (einfacher als für einen freien Schnitt). Ich dachte sogar, dass es offensichtlich sein könnte, aber ich kam nicht weiter. Es ist durchaus möglich, dass ich etwas ganz einfaches verpasse, und wenn dies der Fall ist, würde ich einige Hinweise schätzen! $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
quelle

Sie meinen: Für alle

und für alle

ist der durch

induzierte Teilgraph von

nicht isomorph zu

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Jukka Suomela

Ich denke, dass die Antwort von RJK auf das andere hiermit verbundene Problem auf dieses Problem zutrifft (in der Tat besser als auf das andere Problem).

Tsuyoshi Ito

@Jukka: Ganz genau. Vielen Dank für den Hinweis und verzeihen Sie mir, dass ich zu faul bin (zumindest jetzt), um die Frage entsprechend zu aktualisieren!

Neeldhara

@ Tsuyoshi: Ja, und jetzt habe ich auch hier eine ausführlichere Version der Antwort! Allerdings sollte ich sagen, dass ich dies gepostet habe, weil ich mich in der Situation befunden habe, dass ich eine Straßensperre getroffen habe, während ich über X und Y nachgedacht habe und dies eine verwandte und einfachere Startsituation zu sein scheint. Ich dachte nur, ich sollte die Details von Y für den Rest teilen, der über X

nachdachte

Serge Gaspers verwies auf eine alte (1980) Veröffentlichung von Lewis und Yannakakis, die hier sehr relevant zu sein scheint!

RJK,

Antworten:

Die frühesten Hinweise, die ich auf diese Art von Problem kenne, sind die folgenden. Auf diese wird auch in der Veröffentlichung von Cowen, Goddard und Jesurum Bezug genommen, die ich im anderen Thread erwähnt habe.

Andrews und Jacobson. (1985) Zur Verallgemeinerung der chromatischen Zahl. In Proc. 16. Southeastern International Conference für Kombinatorik, Graphentheorie und Computing (Boca Raton 1985), Congr. Nummer. 47 33–48.

Cowen, Cowen und Woodall. (1986) Fehlerhafte Einfärbungen von Graphen in Oberflächen: Aufteilung in Teilgraphen mit begrenzter Wertigkeit. J. Graph Theory 10 187–195.

Harary. (1985) Bedingte Färbbarkeit in Graphen. In Graphs and Applications (Boulder 1982), Wiley-Interscience, S. 127–136.

Harary und Jones (geborene Fraughnaugh). (1985) Bedingte Färbbarkeit II: Bipartite Variationen. In Proc. Sundance-Konferenz über Kombinatorik und verwandte Themen (Sundance 1985), Congr. Nummer. 50 205–218.

AFAIK, es gibt noch kein Papier, das die explizite P / NP-c-Dichotomie für verschiedene Wahlmöglichkeiten von H enthält. Dies wurde jedoch von Hell und Nesetril für eine andere Art der Verallgemeinerung der chromatischen Zahl "H-Färbungen" durchgeführt ", zu Homomorphismen.

RJK
quelle

Vielen Dank für Ihre sehr detaillierte Antwort - sehr geschätzt. Das ist eine wesentliche Ergänzung zu meiner Leseliste, die mich eine Weile beschäftigen sollte!

Neeldhara

Nun, kein Problem, obwohl es, wie ich bereits erwähnte, neben dem JGT-Papier ziemlich schwierig ist, diese aufzuspüren. (Tatsächlich muss ich zugeben, dass ich bisher noch nicht viel erreicht habe, obwohl ich Zugang zu zahlreichen kanadischen Universitätsbibliotheken hatte.) In jedem Fall ist die Arbeit von Cowen, Goddard und Jesurum wahrscheinlich am relevantesten und beantwortet Ihre / Morons Frage an H ein fester Stern, auch auf ebene Graphen beschränkt. Wahrscheinlich sind Zyklen oder Cliquen die nettesten offenen (ich denke?) Klassen von H, in die man sich verlieben kann.

RJK,

$F_1$ $F_2$ $F_1$ $F_2$ $F_1$ $F_2$

(F-frei = {für alle H in F, H-frei})

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

Aravind
quelle