Partycja wolna od H.

To jest pytanie, zainspirowany problemu cięcia H-darmo . Biorąc pod uwagę wykres, podział jego zbioru wierzchołków na części jest wolny od jeśli nie indukuje kopii dla wszystkich , . $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$

Chciałbym rozważyć następujące pytanie:

To, co najmniej , dla których istnieje -FREE podziałowi części? $r$ $H$ $r$

Zauważ, że gdy jest pojedynczą krawędzią, oznacza to znalezienie liczby chromatycznej i jest już NP-kompletny. Zastanawiam się, czy łatwiej jest wykazać kompletność NP dla dowolnego ustalonego dla tego problemu (łatwiej, w porównaniu do pokazania go dla cięcia bez ). Myślałem nawet, że to oczywiste, ale nigdzie nie dotarłem. Jest całkiem możliwe, że brakuje mi czegoś całkiem prostego, a jeśli tak, to doceniłbym kilka wskazówek! $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
źródło

Masz na myśli: dla wszystkich

dla wszystkich

podgrupa

indukowana przez

nie jest izomorficzna dla

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Jukka Suomela

Myślę, że odpowiedź RJK na inny związany z tym problem dotyczy tego problemu (w rzeczywistości lepiej niż inny problem).

Tsuyoshi Ito

@Jukka: Całkiem tak. Dzięki za wskaźnik i wybacz mi, że jestem zbyt leniwy (przynajmniej na razie), aby odpowiednio zaktualizować pytanie!

Neeldhara,

@Tsuyoshi: Tak, a teraz mam tutaj również bardziej rozbudowaną wersję odpowiedzi! Powinienem jednak powiedzieć, że opublikowałem to, ponieważ znalazłem się w sytuacji „I-hit-a-roadblock-while-thinking-about-X and Y-wydaje się-związany i łatwiejszy start”. Pomyślałem, że powinienem podzielić się szczegółami Y dla reszty, którzy myśleli o X, i to nie było przede wszystkim zamierzone jako prośba o referencje :)

Neeldhara,

Serge Gaspers odniósł się do starego (1980) artykułu Lewisa i Yannakakisa, który wydaje się tutaj bardzo istotny!

RJK

Odpowiedzi:

Najwcześniejsze znane mi odniesienia do tego typu problemów są następujące. Są one również wspomniane w artykule Cowena, Goddarda i Jesuruma, o którym wspominałem w drugim wątku.

Andrews i Jacobson. (1985) O uogólnieniu liczby chromatycznej. W Proc. 16. międzynarodowa konferencja południowo-wschodnia na temat kombinatoryki, teorii grafów i obliczeń (Boca Raton 1985), Congr. Liczba 47 33–48.

Cowen, Cowen i Woodall. (1986) Wadliwe zabarwienie wykresów na powierzchniach: Podziały na podgrupy ograniczonej wartościowości. J. Teoria grafów 10 187–195.

Harary. (1985) Warunkowa kolorystyka na wykresach. W Graphs and Applications (Boulder 1982), Wiley – Interscience, s. 127–136.

Harary i Jones (z domu Fraughnaugh). (1985) Warunkowa kolorystyka II: Wariacje dwustronne. W Proc. Sundance Conference on Combinatorics and Related Topics (Sundance 1985), Congr. Liczba 50 205–218.

AFAIK, nie ma jeszcze dokumentu dającego wyraźną dychotomię P / NP-c dla różnych wyborów H. Zostało to jednak zrobione przez Hell i Nesetril, dla innego rodzaju uogólnienia liczby chromatycznej, „H-coloring „na homomorfizmy.

RJK
źródło

Bardzo dziękuję za bardzo szczegółową odpowiedź - bardzo mile widziane. To znaczący dodatek do mojej listy lektur, powinien przez jakiś czas być zajęty!

Neeldhara,

Cóż, nie ma problemu, chociaż, jak wspomniałem wcześniej, oprócz papieru JGT, bardzo trudno jest je wyśledzić. (W rzeczywistości muszę przyznać, że nie udało mi się jeszcze wiele, mimo że miałem dostęp do wielu kanadyjskich bibliotek uniwersyteckich.) W każdym razie artykuł Cowen, Goddard i Jesurum jest prawdopodobnie najbardziej odpowiedni i odpowiada na pytanie pana / Morona dotyczące H będąc gwiazdą stałą, ograniczoną nawet do grafów płaskich. Prawdopodobnie najpiękniejsze otwarte (jak sądzę?) Klasy H, w które można zatopić zęby, to cykle lub kliki.

RJK

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

(F-free = {dla wszystkich H w F, H-wolny})

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

Aravind
źródło