Homomorfizm wykresu

Homomorfizm od snarka kwiatowego J ₅ do wykresu cyklu C ₅ . Jest to również wycofanie na podwykres na pięciu środkowych wierzchołkach. Tak więc J ₅ jest faktycznie homomorficznie równoważny z rdzeniem C ₅ .

W matematycznej dziedzinie teorii grafów homomorfizm grafów to mapowanie między dwoma grafami , które szanuje ich strukturę. Mówiąc dokładniej, jest to funkcja między zbiorami wierzchołków dwóch grafów, która odwzorowuje sąsiednie wierzchołki na sąsiednie wierzchołki.

Homomorfizmy uogólniają różne pojęcia kolorowania grafów i pozwalają na wyrażenie ważnej klasy problemów spełniania ograniczeń , takich jak pewne problemy z szeregowaniem lub przydziałem częstotliwości . Fakt, że można składać homomorfizmy, prowadzi do bogatych struktur algebraicznych: preorder na grafach, sieć rozdzielcza i kategoria (jedna dla grafów nieskierowanych, a druga dla grafów skierowanych). Złożoność obliczeniowa znalezienie homomorfizmu między danymi wykresami jest ogólnie niemożliwe, ale wiele wiadomo o szczególnych przypadkach, które można rozwiązać w czasie wielomianowym . Granice między przypadkami możliwymi do rozwiązania i trudnymi do rozwiązania były aktywnym obszarem badań.

Definicje

W tym artykule, o ile nie zaznaczono inaczej, grafy są skończonymi, nieskierowanymi grafami z dozwolonymi pętlami , ale niedozwolonymi wieloma krawędziami (równoległymi). Homomorfizm wykresu $f$ z wykresu do wykresu ${\ Displaystyle G = ($ V ${\ Displaystyle H = (V (H), E (H))}$ , napisane

f : G \to H

jest funkcją od $(G)}$ $H$ do $)}$ $H$ , która odwzorowuje punkty końcowe każdej krawędzi w punktach końcowych krawędzi w . Formalnie ${\ Displaystyle \ {u, v \} \ w E (G)}$ implikuje ${\ Displaystyle \ {f (u), f (v) \} \ in E (H)}$ , dla wszystkich par wierzchołków ${\ Displaystyle u, v}$ w ${\ Displaystyle V (G)}$ . Jeśli istnieje jakikolwiek homomorfizm od G do H , to mówi się, że G jest homomorficzny z H lub H -kolorowalny . Jest to często oznaczane jako po prostu:

G \to H._

Powyższa definicja jest rozszerzona na grafy skierowane. Wtedy dla homomorfizmu f : G → H , ( f ( u ), f ( v )) jest łukiem (skierowaną krawędzią) H zawsze, gdy ( u , v ) jest łukiem G .

Istnieje homomorfizm iniekcyjny od G do H (tj. taki, który nigdy nie odwzorowuje różnych wierzchołków na jeden wierzchołek) wtedy i tylko wtedy, gdy G jest podgrafem H . Jeśli homomorfizm f : G → H jest bijekcją (zgodnością jeden do jednego między wierzchołkami G i H ), której funkcją odwrotną jest również homomorfizm grafu, to f jest izomorfizmem grafu .

Mapy pokrycia są szczególnym rodzajem homomorfizmów, które odzwierciedlają definicję i wiele właściwości map pokrycia w topologii . Są one definiowane jako surjektywne homomorfizmy (tj. coś jest odwzorowywane na każdy wierzchołek), które są również lokalnie bijekcyjne, to znaczy bijekcja na sąsiedztwo każdego wierzchołka. Przykładem jest dwudzielna podwójna pokrywa , utworzona z grafu przez podzielenie każdego wierzchołka v na v ₀ i v ₁ i zastąpienie każdej krawędzi u , v krawędziami u ₀ , v ₁ i v ₀ , u ₁ . Odwzorowanie funkcji v ₀ i v ₁ w okładce na v na oryginalnym wykresie jest homomorfizmem i mapą pokrycia.

Homeomorfizm grafów to inne pojęcie, niezwiązane bezpośrednio z homomorfizmami. Z grubsza mówiąc, wymaga iniekcji, ale umożliwia mapowanie krawędzi na ścieżki (nie tylko na krawędzie). Graph minors to jeszcze bardziej zrelaksowany pomysł.

Rdzenie i wycofania

K ₇ , kompletny graf z 7 wierzchołkami, jest rdzeniem.

Dwa wykresy G i H są homomorficznie równoważne, jeśli G → H i H → G . Mapy niekoniecznie są surjektywne ani iniekcyjne. Na przykład kompletne grafy dwudzielne K _2,2 i K _3,3 są homomorficznie równoważne: każde odwzorowanie można zdefiniować jako obejmujące lewą (odpowiednio prawą) połowę grafu dziedziny i odwzorowanie tylko jednego wierzchołka po lewej stronie (odpowiednio prawą) . po prawej) połowa wykresu obrazu.

Wycofanie jest homomorfizmem r z grafu G do podgrafu H z G takiego, że r ( v ) = v dla każdego wierzchołka v z H . W tym przypadku podgraf H jest nazywany retrakcją G .

Rdzeń jest grafem, który nie ma homomorfizmu z żadnym właściwym podgrafem . Równoważnie rdzeń można zdefiniować jako graf, który nie cofa się do żadnego właściwego podgrafu. Każdy graf G jest homomorficznie równoważny z unikalnym rdzeniem (z dokładnością do izomorfizmu), zwanym rdzeniem G . Warto zauważyć, że ogólnie nie jest to prawdą w przypadku grafów nieskończonych. Jednak te same definicje dotyczą grafów skierowanych, a graf skierowany jest również odpowiednikiem unikalnego rdzenia. Każdy graf i każdy graf skierowany zawiera swój rdzeń w postaci retraktu i podgrafu indukowanego .

Na przykład wszystkie pełne grafy K _n i wszystkie nieparzyste cykle ( wykresy cykli o nieparzystej długości) są rdzeniami. Każdy trójkolorowy graf G , który zawiera trójkąt (tzn. ma pełny graf K ₃ jako podgraf) jest homomorficznie równoważny K ₃ . Dzieje się tak dlatego, że z jednej strony 3-kolorowanie G jest tym samym, co homomorfizm G → K ₃ , jak wyjaśniono poniżej. Z drugiej strony każdy podgraf G trywialnie dopuszcza homomorfizm w G , implikując K ₃ → G . Oznacza to również, że K ₃ jest rdzeniem każdego takiego grafu G . Podobnie każdy graf dwudzielny , który ma co najmniej jedną krawędź, jest równoważny K ₂ .

Połączenie z kolorowaniami

K - kolorowanie dla pewnej liczby całkowitej k jest przypisaniem jednego z k kolorów do każdego wierzchołka grafu G w taki sposób, że punkty końcowe każdej krawędzi mają różne kolory. K - kolorowania G odpowiadają dokładnie homomorfizmom od G do pełnego grafu K _k . Rzeczywiście, wierzchołki K _k odpowiadają k kolorom , a dwa kolory sąsiadują ze sobą jako wierzchołki K _k wtedy i tylko wtedy, gdy są różne. Stąd funkcja definiuje homomorfizm na K _k wtedy i tylko wtedy, gdy odwzorowuje sąsiednie wierzchołki G na różne kolory (tj. jest to k -kolorowanie). W szczególności, G jest k -kolorowalna wtedy i tylko wtedy, gdy jest K _k -kolorowalna.

Jeśli istnieją dwa homomorfizmy G → H i H → K _k , to ich złożenie G → K _k również jest homomorfizmem. Innymi słowy, jeśli graf H można pokolorować k kolorami i istnieje homomorfizm od G do H , to G można również pokolorować k . Dlatego G → H implikuje χ( G ) ≤ χ( H ), gdzie χ oznacza liczbę chromatyczną grafu (najmniejsze k , dla którego można go pokolorować k ).

Warianty

Ogólne homomorfizmy można również traktować jako rodzaj kolorowania: jeśli wierzchołki ustalonego grafu H są dostępnymi kolorami , a krawędzie H opisują, które kolory są zgodne , to H -kolorowanie G jest przypisaniem kolorów wierzchołkom grafu G takie, że sąsiednie wierzchołki uzyskują kompatybilne kolory. Wiele koncepcji kolorowania grafów pasuje do tego wzorca i można je wyrazić jako homomorfizmy grafów w różnych rodzinach grafów. Zabarwienia kołowe można zdefiniować za pomocą homomorfizmów okrągłych pełnych wykresów , udoskonalając zwykłe pojęcie kolorowania. b -krotne Zabarwienie ułamkowe i można zdefiniować za pomocą homomorfizmów w grafach Knesera . Kolory T odpowiadają homomorfizmom w pewne nieskończone grafy. Zorientowane kolorowanie grafu skierowanego jest homomorfizmem dowolnego grafu zorientowanego . Kolorowanie L (2,1) jest homomorfizmem dopełnienia wykresu ścieżki to jest lokalnie iniekcyjne, co oznacza, że musi być iniekcyjne w sąsiedztwie każdego wierzchołka.

Orientacje bez długich ścieżek

Inne ciekawe powiązanie dotyczy orientacji grafów. Orientacja grafu nieskierowanego G to dowolny graf skierowany uzyskany przez wybranie jednej z dwóch możliwych orientacji dla każdej krawędzi. Przykładem orientacji pełnego grafu K _k jest turniej przechodni T → _k z wierzchołkami 1,2,…, k i łukami od i do j zawsze, gdy i < j . Homomorfizm między orientacjami grafów G i H daje homomorfizm między nieskierowanymi grafami G i H , po prostu pomijając orientacje. Z drugiej strony, biorąc pod uwagę homomorfizm G → H między grafami nieskierowanymi, dowolną orientację H → z H można cofnąć do orientacji G → z G , tak że G → ma homomorfizm z H → . Dlatego wykres G to k -kolorowalna (ma homomorfizm do K _k ) wtedy i tylko wtedy, gdy pewna orientacja G ma homomorfizm do T → _k .

Twierdzenie folklorystyczne mówi, że dla każdego k graf skierowany G ma homomorfizm do T → _k wtedy i tylko wtedy, gdy nie dopuszcza żadnego homomorfizmu ze ścieżki skierowanej P → _{k +1} . Tutaj P → _n jest grafem skierowanym z wierzchołkami 1, 2, …, n i krawędziami od i do i + 1, dla i = 1, 2, …, n − 1. Dlatego graf to k -kolorowalny wtedy i tylko wtedy, gdy ma orientację, która nie dopuszcza żadnego homomorfizmu z P → _{k +1} . Twierdzenie to można nieco wzmocnić, mówiąc, że graf jest k -kolorowalny wtedy i tylko wtedy, gdy pewna orientacja nie zawiera skierowanej ścieżki o długości k (brak P → _{k +1} jako podgrafu). To jest twierdzenie Gallai-Hasse-Roy-Vitavera .

Związek z problemami spełniania ograniczeń

Przykłady

Wykres H nienastępujących po sobie dni tygodnia, izomorficzny z wykresem dopełnienia C ₇ i kołową kliką K _7/2

Niektóre problemy z szeregowaniem można modelować jako pytanie o znalezienie homomorfizmów grafów. Przykładowo, można chcieć przypisać kursy warsztatowe do przedziałów czasowych w kalendarzu, tak aby dwa kursy, w których uczestniczy ten sam student, nie były zbyt blisko siebie w czasie. Kursy tworzą wykres G z krawędzią między dowolnymi dwoma kursami, w których uczestniczy jakiś wspólny student. Szczeliny czasowe tworzą wykres H , z krawędzią pomiędzy dowolnymi dwoma szczelinami, które są wystarczająco odległe w czasie. Na przykład, jeśli ktoś chce mieć cykliczny, tygodniowy harmonogram, taki, że każdy uczeń otrzymuje swoje kursy warsztatowe w dni nienastępujące po sobie, to H byłby wykresem dopełnienia C 7 _. Homomorfizm grafu od G do H jest więc harmonogramem przypisującym kursy do określonych przedziałów czasowych. Aby dodać wymaganie, że np. żaden student nie ma kursów jednocześnie w piątek i poniedziałek, wystarczy usunąć odpowiednią krawędź z H .

Prosty problem alokacji częstotliwości można przedstawić w następujący sposób: pewna liczba nadajników w sieci bezprzewodowej musi wybrać kanał częstotliwości, na którym będą transmitować dane. Aby uniknąć zakłóceń , nadajniki, które są geograficznie blisko, powinny używać kanałów o częstotliwościach, które są daleko od siebie. Jeśli ten warunek zostanie przybliżony pojedynczym progiem definiującym „geograficznie blisko” i „daleko od siebie”, wówczas prawidłowy wybór kanału ponownie odpowiada homomorfizmowi grafu. Powinien wyjść z wykresu nadajników G , z krawędziami między parami, które są geograficznie blisko, do wykresu kanałów H , z krawędziami między kanałami, które są daleko od siebie. Chociaż ten model jest dość uproszczony, dopuszcza pewną elastyczność: pary nadajników, które nie są blisko siebie, ale mogą zakłócać ze względu na cechy geograficzne, można dodać do krawędzi G . Ci, którzy nie komunikują się w tym samym czasie, mogą zostać z niego usunięci. Podobnie, pary kanałów, które są daleko od siebie, ale wykazują zakłócenia harmoniczne , mogą zostać usunięte z zestawu brzegowego H.

W każdym przypadku te uproszczone modele przedstawiają wiele problemów, z którymi trzeba się uporać w praktyce. Problemy spełnienia ograniczeń , które uogólniają problemy homomorfizmu grafów, mogą wyrażać różne dodatkowe typy warunków (takie jak indywidualne preferencje lub ograniczenia liczby pokrywających się przypisań). Dzięki temu modele stają się bardziej realistyczne i praktyczne.

Widok formalny

Grafy i grafy skierowane można postrzegać jako szczególny przypadek znacznie bardziej ogólnego pojęcia zwanego strukturami relacyjnymi (zdefiniowanymi jako zbiór z krotką relacji). Grafy skierowane to struktury z pojedynczą relacją binarną (sąsiedztwem) w dziedzinie (zbiór wierzchołków). Zgodnie z tym poglądem homomorfizmy takich struktur są dokładnie homomorfizmami grafów. Ogólnie rzecz biorąc, kwestia znalezienia homomorfizmu z jednej struktury relacyjnej do drugiej jest problemem spełniania ograniczeń (CSP). Przypadek grafów daje konkretny pierwszy krok, który pomaga zrozumieć bardziej skomplikowane CSP. Wiele algorytmicznych metod znajdowania homomorfizmów grafów, takich jak śledzenie wsteczne , propagacja ograniczeń i wyszukiwanie lokalne , ma zastosowanie do wszystkich CSP.

W przypadku grafów G i H pytanie, czy G ma homomorfizm z H , odpowiada instancji CSP z tylko jednym rodzajem ograniczeń, jak następuje. Zmiennymi są wierzchołki G , a dziedziną każdej zmiennej jest zbiór wierzchołków H. Ocena jest funkcją, która przypisuje każdej zmiennej element dziedziny, więc funkcja f od V ( G ) do V ( H ). Każda krawędź lub łuk ( u , v ) G odpowiada zatem wiązaniu ( ( u , v ), E( H )). Jest to ograniczenie wyrażające, że ocena powinna odwzorować łuk ( u , v ) na parę ( f ( u ), f ( v )), która jest w relacji E ( H ), czyli na łuk H . Rozwiązaniem CSP jest ocena uwzględniająca wszystkie ograniczenia, więc jest to dokładnie homomorfizm od G do H .

Struktura homomorfizmów

Złożenia homomorfizmów są homomorfizmami. W szczególności relacja → na grafach jest przechodnia (i zwrotna, trywialnie), więc jest to preorder na grafach. Niech klasa równoważności grafu G przy równoważności homomorficznej będzie [ G ]. Klasa równoważności może być również reprezentowana przez unikalny rdzeń w [ G ]. Relacja → jest częściowym porządkiem na tych klasach równoważności; definiuje pozę .

Niech G < H oznacza, że istnieje homomorfizm od G do H , ale nie ma homomorfizmu od H do G . Relacja → jest rzędem gęstym , co oznacza, że dla wszystkich (nieskierowanych) grafów G , H takich, że G < H , istnieje graf K taki, że G < K < H (to dotyczy poza trywialnymi przypadkami G = K ₀₀ lub K1 ₎ . Na przykład pomiędzy dowolnymi dwoma grafami pełnymi (oprócz K , K ₁ , K ₂ ) istnieje nieskończenie wiele pełnych grafów kołowych , odpowiadających liczbom wymiernym między liczbami naturalnymi.

Zbiór klas równoważności grafów pod homomorfizmami to sieć rozdzielcza , z połączeniem [ G ] i [ H ] zdefiniowanym jako (klasa równoważności) związek rozłączny [ G ∪ H ] i spotkanie [ G ] i [ H ] zdefiniowany jako iloczyn tensorowy [ G × H ] (wybór wykresów G i H reprezentujących klasy równoważności [ G ] i [ H ] nie ma znaczenia). Nieredukowalne elementy tej sieci są grafami dokładnie spójnymi . Można to pokazać za pomocą faktu, że homomorfizm odwzorowuje spójny graf na jeden spójny składnik grafu docelowego. Nieredukowalne elementy tej sieci są dokładnie grafami multiplikatywnymi . Są to wykresy K takie, że iloczyn G × H ma homomorfizm z K tylko wtedy, gdy jeden z G lub H też robi. Identyfikacja grafów multiplikatywnych leży u podstaw hipotezy Hedetniemiego .

Homomorfizmy grafów również tworzą kategorię , z wykresami jako obiektami, a homomorfizmami jako strzałkami. Obiektem początkowym jest pusty graf, a obiektem końcowym jest graf z jednym wierzchołkiem i jedną pętlą w tym wierzchołku. Iloczyn tensorowy grafów jest iloczynem teorii kategorii , a wykres wykładniczy jest obiektem wykładniczym dla tej kategorii. Ponieważ te dwie operacje są zawsze zdefiniowane, kategoria grafów jest zamkniętą kategorią kartezjańską . Z tego samego powodu krata klas równoważności grafów pod homomorfizmami jest w rzeczywistości algebrą Heytinga .

W przypadku grafów skierowanych obowiązują te same definicje. W szczególności → jest częściowym porządkiem klas równoważności grafów skierowanych. Różni się od porządku → według klas równoważności grafów nieskierowanych, ale zawiera go jako podrząd. Dzieje się tak, ponieważ każdy graf nieskierowany można traktować jako graf skierowany, w którym każdy łuk ( u , v ) występuje razem z jego łukiem odwrotnym ( v , u ), co nie zmienia definicji homomorfizmu. Kolejność → dla grafów skierowanych to ponownie siatka rozdzielcza i algebra Heytinga, z operacjami łączenia i spotykania zdefiniowanymi jak poprzednio. Nie jest jednak gęsty. Istnieje również kategoria z grafami skierowanymi jako obiektami i homomorfizmami jako strzałkami, czyli znowu a zamkniętej kategorii kartezjańskiej .

Nieporównywalne wykresy

Graf Grötzscha, nieporównywalny z K ₃

Istnieje wiele nieporównywalnych grafów pod względem preorderu homomorfizmu, to znaczy par grafów, z których żaden nie dopuszcza homomorfizmu w drugim. Jednym ze sposobów ich skonstruowania jest rozważenie nieparzystego obwodu grafu G , długości jego najkrótszego cyklu o nieparzystej długości. Nieparzysty obwód jest równoważnie najmniejszą liczbą nieparzystą g , dla której istnieje homomorfizm z wykresu cyklu na wierzchołkach g do G . Z tego powodu, jeśli G → H , to nieparzysty obwód G jest większy lub równy nieparzystemu obwodowi H .

Z drugiej strony, jeśli G → H , to liczba chromatyczna G jest mniejsza lub równa liczbie chromatycznej H . Dlatego jeśli G ma ściśle większy obwód nieparzysty niż H i ściśle większą liczbę chromatyczną niż H , to G i H są nieporównywalne. Na przykład graf Grötzscha jest 4-chromatyczny i nie zawiera trójkątów (ma obwód 4 i obwód nieparzysty 5), więc jest nieporównywalny z grafem trójkątnym K ₃ .

Przykładami grafów z dowolnie dużymi wartościami nieparzystego obwodu i liczby chromatycznej są grafy Knesera i uogólnione mycielskie . Sekwencja takich grafów, przy jednoczesnym zwiększaniu wartości obu parametrów, daje nieskończenie wiele nieporównywalnych grafów (antyłańcuch w preorderze homomorfizmu). Inne właściwości, takie jak gęstość preorderu homomorfizmu, można udowodnić za pomocą takich rodzin. Konstrukcje grafów z dużymi wartościami liczby chromatycznej i obwodu, nie tylko nieparzystego obwodu, są również możliwe, ale bardziej skomplikowane (patrz Kolorowanie obwodu i wykresu ).

Wśród grafów skierowanych znacznie łatwiej jest znaleźć nieporównywalne pary. Rozważmy na przykład skierowane grafy cykli C → _n , z wierzchołkami 1, 2, …, n i krawędziami od i do i + 1 (dla i = 1, 2, …, n − 1) oraz od n do 1. Tam jest homomorfizmem od C → _n do C → _k ( n , k ≥ 3) wtedy i tylko wtedy, gdy n jest wielokrotnością k . W szczególności skierowane wykresy cykli C → _n z n liczbą pierwszą są nieporównywalne.

Złożoność obliczeniowa

W problemie homomorfizmu grafów przykładem jest para grafów ( G , H ), a rozwiązaniem jest homomorfizm od G do H . Ogólny problem decyzyjny , pytający, czy istnieje jakieś rozwiązanie, jest NP-zupełny . Jednak ograniczanie dozwolonych instancji powoduje wiele różnych problemów, z których niektóre są znacznie łatwiejsze do rozwiązania. Metody, które stosuje się przy unieruchamianiu lewej strony G, są zupełnie inne niż dla prawej strony H , ale w każdym przypadku znana lub przypuszczana jest dychotomia (ostra granica między przypadkami łatwymi i trudnymi).

Homomorfizmy do grafu ustalonego

Problem homomorfizmu ze stałym grafem H po prawej stronie każdej instancji jest również nazywany problemem H -kolorowania. Gdy H jest grafem zupełnym K _k , jest to problem k -kolorowania wykresu , który jest rozwiązywalny w czasie wielomianowym dla k = 0, 1, 2, aw przeciwnym razie NP-zupełny . W szczególności, K2 _- kolorystyka grafu G jest równoważna temu, że G jest dwudzielny ₀ , który można przetestować w czasie liniowym. _Bardziej ogólnie, gdy H jest grafem dwudzielnym, H -kolorowalność jest równoważna z K2 _- kolorowalność (lub K / K1 -kolorowalność, gdy H jest pusty/bez krawędzi), stąd równie łatwo zdecydować. Pavol Hell i Jaroslav Nešetřil udowodnili, że w przypadku grafów nieskierowanych żaden inny przypadek nie jest możliwy do rozwiązania:

Twierdzenie Hella-Nešetřila (1990): Problem z kolorowaniem H występuje w P, gdy H jest dwudzielny, aw przeciwnym razie NP-zupełny.

Jest to również znane jako twierdzenie o dychotomii dla (nieskierowanych) homomorfizmów grafów, ponieważ dzieli problemy z kolorowaniem H na problemy NP-zupełne lub problemy P, bez przypadków pośrednich . W przypadku grafów skierowanych sytuacja jest bardziej skomplikowana iw rzeczywistości odpowiada znacznie bardziej ogólnemu pytaniu o charakteryzację złożoności problemów spełniania ograniczeń . Okazuje się, że H dla grafów skierowanych są tak samo ogólne i tak różnorodne, jak CSP z wszelkimi innymi rodzajami ograniczeń. Formalnie, (skończony) język ograniczeń (lub szablon ) Γ jest skończoną dziedziną i skończonym zbiorem relacji w tej dziedzinie. CSP( Γ ) to problem spełnienia ograniczeń, w którym instancje mogą używać ograniczeń tylko w Γ .

Twierdzenie (Feder, Vardi 1998): Dla każdego języka z ograniczeniami Γ problem CSP( Γ ) jest równoważny w przypadku redukcji w czasie wielomianowym z pewnym problemem H -kolorowania dla pewnego skierowanego grafu H .

Intuicyjnie oznacza to, że każda technika algorytmiczna lub wynik złożoności, który ma zastosowanie do problemów z kolorowaniem H dla grafów skierowanych H , równie dobrze odnosi się do ogólnych CSP. W szczególności można zapytać, czy twierdzenie Hella-Nešetřila można rozszerzyć na grafy skierowane. Zgodnie z powyższym twierdzeniem jest to równoważne z hipotezą Federa – Vardiego (inaczej hipotezą CSP, hipotezą dychotomii) dotyczącą dychotomii CSP, która stwierdza, że dla każdego języka z ograniczeniami Γ , CSP ( Γ ) jest NP-zupełne lub w P. Przypuszczenie to zostało udowodnione w 2017 roku niezależnie przez Dmitrija Żuka i Andrieja Bułatowa, co prowadzi do następującego wniosku:

Wniosek (Bulatov 2017; Zhuk 2017): Problem z kolorowaniem H na grafach skierowanych, dla ustalonego H , jest P lub NP-zupełny.

Homomorfizmy z ustalonej rodziny grafów

Problem homomorfizmu z pojedynczym ustalonym wykresem G po lewej stronie instancji wejściowych można rozwiązać brutalnie w czasie | V ( H ) | ^{O(| V ( G )|)} , więc wielomian w rozmiarze grafu wejściowego H . Innymi słowy, problem jest trywialny w P dla grafów G o ograniczonym rozmiarze. Interesującym pytaniem jest zatem, jakie inne właściwości G , poza rozmiarem, umożliwiają algorytmy wielomianowe.

Kluczową właściwością okazuje się być treewidth , miara tego, jak drzewny jest graf. Dla wykresu G o szerokości drzewa co najwyżej k i wykresu H problem homomorfizmu można rozwiązać w czasie | V ( H ) | ^{O( k )} ze standardowym podejściem do programowania dynamicznego . W rzeczywistości wystarczy założyć, że rdzeń G ma co najwyżej szerokość drzewa k . Dzieje się tak nawet wtedy, gdy rdzeń nie jest znany.

Wykładnik w | V ( H ) | Algorytm czasu ^{O( k )} nie może być znacznie obniżony: brak algorytmu z czasem działania | V ( H ) | ^{o(tw( G ) /log tw( G ))} istnieje, zakładając hipotezę czasu wykładniczego (ETH), nawet jeśli dane wejściowe są ograniczone do dowolnej klasy grafów o nieograniczonej szerokości drzewa. ETH jest nieudowodnionym założeniem podobnym do P ≠ NP , ale silniejszy. Przy tym samym założeniu zasadniczo nie ma również innych właściwości, których można by użyć do uzyskania algorytmów czasu wielomianowego. Jest to sformalizowane w następujący sposób:

Twierdzenie ( Grohe ): Dla obliczalnej

}}}

grafów problem homomorfizmu dla przypadków

{\ Displaystyle (G, H)}

)

sol

\ displaystyle G \ in {\ mathcal {

mają

jest w P wtedy i tylko wtedy, gdy wykresy w rdzenie o ograniczonej szerokości drzewa (zakładając ETH).

Można zapytać, czy problem jest przynajmniej rozwiązywalny w czasie dowolnie silnie zależnym od G , ale z ustaloną zależnością wielomianową od wielkości H . Odpowiedź jest ponownie pozytywna, jeśli ograniczymy G do klasy grafów z rdzeniami o ograniczonej szerokości drzewa i ujemna dla każdej innej klasy. W języku sparametryzowanej złożoności formalnie stwierdza się, że problem homomorfizmu w $sparametryzowanym$ przez rozmiar (liczbę krawędzi) wykazuje dychotomię. To jest wykonalne ze stałymi parametrami , jeśli wykresy w $mają$ o ograniczonej szerokości drzewa, a W [1] -zupełne w przeciwnym razie.

Te same stwierdzenia odnoszą się bardziej ogólnie do problemów spełniania ograniczeń (lub innymi słowy do struktur relacyjnych). Jedynym potrzebnym założeniem jest to, że ograniczenia mogą dotyczyć tylko ograniczonej liczby zmiennych (wszystkie relacje mają pewną ograniczoną arity, 2 w przypadku grafów). Odpowiednim parametrem jest zatem szerokość drzewa pierwotnego grafu ograniczeń .

Zobacz też

Słowniczek terminów z teorii grafów
Homomorfizm , dla tego samego pojęcia na różnych strukturach algebraicznych
Przepisywanie wykresu
Wykresy medianowe , definiowane jako retrakty hipersześcianów
przypuszczenie Sidorenko

Notatki

Ogólne książki i ekspozycje

Cameron, P. (2006), Homomorfizmy grafów, notatki grupy badawczej kombinatoryki (PDF)
Piekło, Paweł ; Nešetřil, Jaroslav (2004), Grafy i homomorfizmy , Oxford Lecture Series in Mathematics and Its Applications, tom. 28, Oxford University Press, ISBN 0-19-852817-5
Hahn, G.; Tardif, C. (1997), „Homomorfizmy grafów: struktura i symetria” , Symetria grafów: metody i zastosowania algebraiczne (PDF) , Springer, s. 107–166, doi : 10.1007 / 978-94-015-8937-6_4
Godsil, C .; Royle, G. (2001), „6. Homomorfizmy”, Algebraic Graph Theory , Graduate Texts in Mathematics, tom. 207, Springer-Verlag Nowy Jork, doi : 10.1007/978-1-4613-0163-9 , ISBN 978-1-4613-0163-9

W spełnieniu ograniczeń i algebrze uniwersalnej

Bodirsky, M. (2007), Homomorfizmy grafów i algebra uniwersalna , notatki z kursu (PDF)
Piekło, Paweł ; Nešetřil, Jaroslav (2008), „Kolorowanie, spełnianie ograniczeń i złożoność” (PDF) , Computer Science Review , 2 (3): 143–163, doi : 10.1016/j.cosrev.2008.10.003

W teorii sieci i teorii kategorii

Brązowy, R.; Morris, I.; Shrimpton, J.; Wensley, CD (2008), „Wykresy morfizmów grafów” , Electronic Journal of Combinatorics , 15 (1): A1, doi : 10.37236/919
Gray, CT (2014), The Digraph Lattice (PDF) ( AMSI Vacation Research Scholarships , raport z badań studenckich nadzorowany przez Briana Daveya i Jane Pitkethly, La Trobe University ).