Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości

17

Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia w teorii grup, więc wolałbym artykuły, które wykorzystują teorię grupy w delikatny sposób (moje tło jest w CS).GIP

DurgaDatta
źródło
1
Nie mam tej książki (niestety), ale problem z izomorfizmem grafowym: jej złożoność strukturalna Johannesa Köblera, Uwe Schöninga i Jacobo Torána może zawierać dowód na przypadek ograniczonego stopnia. Możesz to sprawdzić.
Tsuyoshi Ito
2
@TsuyoshiIto: Chociaż jest to doskonała książka, która daje dobre wprowadzenie do GI i dość ogólnej ogólnej złożoności strukturalnej, nie zawiera wiele (jeśli w ogóle) na temat ograniczonego stopnia. Nie znam łagodnego wstępu do przypadku ograniczonego stopnia, ale jest on tak ściśle związany z metodami teorii grup, że wątpię, by istniała ekspozycja, która używa teorii grupy „tylko delikatnie” (zgodnie z żądaniem PO).
Joshua Grochow
Chciałbym przedstawić przegląd, zrobię to wkrótce!
Jim

Odpowiedzi:

14

Algorytm grafu izomorficznego z ograniczonym stopniem jest tak ściśle związany z teorią grup (permutacji), że wątpię, by istniał wstęp, który używa grup „tylko delikatnie”. Możesz jednak skonsultować się z doktorem Paolo Codenottiego. praca dyplomowa dla pełniejszego tła. Nie obejmuje dokładnie izomorfizmu grafu ograniczonego stopnia, ale obejmuje potrzebne do niego narzędzia (a reszta pracy dotyczy hipergraphów ograniczonej rangi, rozszerzając najbardziej znany algorytm ogólnego izomorfizmu grafowego na przypadek hipergraphu ograniczonej rangi) .

Przyda ci się również książka Algorytmy teoretyki grupowej i izomorfizm wykresów , ponieważ obejmuje ona większość niezbędnego tła (rozdział 2, „Podstawowe pojęcia”, ma 47 stron) i jest znacznie bardziej spokojną ekspozycją niż większość opublikowanych artykułów na temat temat.

Joshua Grochow
źródło
1

Oznaczenie: Niech jest wykresem, e = ( V, 1 , V, 2 ), krawędź X . Zestaw wierzchołek V k oznacza zbiór wierzchołków odległości k od E i pozwolić H mieć wysokość X .X=(V,E)e=(v1,v2)XVkkehX

Zgodnie z definicją , V = V 0V 1V h oraz V ( h + 1 ) = . Pozwolić, podzbiór e k o krawędziach X ( 0 k H ) jest zdefiniowany ASVkV=V0V1VhV(h+1)=EkX(0kh)

Ek={(u,w)|uVk,wVkV(k+1)}.

Podgrupa jest zdefiniowana jako-Xi

Xk=(V0V1Vk,E0E1E(k1)}

Na przykład X2={(V0V1V2,E0E1)}

to grupa automorfizmów na wykresie X, w której e jest ustalone. Jeśli B jest zbiorem wytwórczych A u t e ( X k ) , piszemyB = u t e ( X k ) , na przykład, jest oczywiste, że u t e ( X 0 ) = ( v 1 , wer. 2Aute(X)XeBAute(Xk)B=Aute(Xk) Gdzie ( v 1 , V, 2 ) jest permutacją wierzchołków v 1 , v 2 o X .Aute(X0)=(v1,v2)(v1,v2)v1,v2X

Zasada Konstruowanie zespołu generującego grupę automorfizmów jest kompletnym problemem GI (graf izomorfizm) [1]. Jeśli więc możemy obliczyć generujący zbiór grupy automorfizmów X (który ograniczył wartościowość w czasie wielomianowym), możemy rozwiązać GI w czasie wielomianowym. Tak więc chcemy ustalić A u t e ( X ) .XXAute(X)

Technika:

Zbudujemy . Dla każdej X k mamy skonstruuje A u t e ( X ( k ) )X0,X1.....XhXkAute(X(k))

Należy zauważyć, że permutacją może być rozszerzony do automorfizmem A u t e ( X ( k + 1 ) ) .Aute(X(k))Aute(X(k+1))

Tak więc, generatory U t e ( x ( k + 1 ) ) można otrzymać z generatorów o A u t e ( X k ) .Aute(X(k+1))Aute(Xk)

Do generatora budowy, struktura, typ jest manipulowany. Konstrukcja-typ E k mogą być podzielone na klasy skończonych. Na przykład w przypadku trójwartościowym istnieje tylko sześć typów (w rzeczywistości może wystąpić tylko pięć takich przypadków).EkEk

Sklasyfikujemy krawędzie w do typów i zgrupujemy je w rodziny. Pomaga to stworzyć wiele unikalnych etykiet.Ek

W przypadku stałej wartościowości liczba etykiet jest niewielka. W tym momencie używamy koncepcji stabilizatorów ustawionych w celu znalezienia permutacji, które działają na konkretną etykietę. W tym procesie znajdujemy generator . Następnie używamy generator A u t e ( X ( k ) ) , aby znaleźć generator A u t e ( X ( k + 1 ) ) , jak wspomniano wcześniej. Postępując w ten sposób, otrzymujemy: A uAute(X(k))Aute(X(k))Aute(X(k+1))Aute(X)

Jim
źródło
[1] Mathon, Rudolf. , Uwaga na wykresie problemu liczenia izomorfizmów, Inform. Proces. Łotysz. 8 (1979), no. 3, 131–132.
Jim