Złożoność rozpoznawania grafów przechodnich werteksów

16

Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik.

Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla wierzchołków?GnnG

Przypomnij sobie, że wykres jest przechodni na wierzchołki, jeśli działa tranzytowo naGAut(G)V(G).

Nie jestem pewien, czy powyższa definicja dopuszcza algorytm wielomianowy, ponieważ może być tak, że kolejność jest wykładnicza.Aut(G)

Jednak wykresy przechodnie wierzchołków mają pewne inne właściwości strukturalne, które można wykorzystać, aby móc je skutecznie określić, więc nie jestem pewien, jaki jest status powyższego pytania.

Kolejną interesującą podklasą grafów przechodnich werteksów, która ma jeszcze większą strukturę, jest klasa grafów Cayleya . Naturalne jest zatem postawienie następującego powiązanego pytania

Pytanie 2. Jaka jest złożoność obliczeniowa ustalenia, czy wykres jest wykresem Cayleya?G

Jernej
źródło
3
Chociaż grupa automorfizmów może być nadwykładnicza, myślę, że można ją przedstawić w przestrzeni wielomianowej, ponieważ minimalna liczba generatorów jest co najwyżej logarytmiczna w |Aut(G)|
Timothy Sun
2
Zauważ, że każdy wykres przechodni wierzchołków jest wykresem Cayleya-Schriera: istnieje jakaś grupa z zestawem generującym S i podgrupą H, tak że wierzchołkami wykresu są cosety G / H , a dwie cosy są połączone krawędzią, jeśli niektóre element S przenosi się jeden na drugi. GSHG/HS
Joshua Grochow

Odpowiedzi:

14

Nie mam pełnej odpowiedzi, ale myślę, że oba problemy są otwarte.


Artykuł Jajcaya, Malniča, Marušiča [3] dotyczy twojego pierwszego pytania. Zapewniają niektóre narzędzia do testowania przechodniości wierzchołków. We wstępie mówią, że:

Dla danego grafu skończonego zdecydowanie trudno jest ustalić, czy Γ jest przechodnie na wierzchołki, a ostateczna odpowiedź pojawia się zwykle dopiero po określeniu znacznej części pełnej grupy automorfizmów Γ .ΓΓΓ

Należy zauważyć, że test przechodniości wierzchołków można wykonać, testując izomorfizm grafu razy. Wykonaj dwie kopie G i G swojego wykresu, ze specjalnymi kotwicami (jak ścieżki o długości n + 1 ) przy u V ( G ) i v V ( G ) . Pomiędzy G i G występuje izomorfizm tylko wtedy, gdy oryginalny wykres ma automorfizm odwzorowujący u na v . W ten sposób można przetestować czułość wierzchołków, ustalając wierzchołekn1GGn+1uV(G)vV(G)GGuv i sprawdzenie, czy istnieją automorfizmy mapujące x na wszystkie pozostałe wierzchołki.xx

Zauważ też, że jeśli test przechodniości wierzchołków można wykonać w czasie wielomianowym, to tak samo jest z testem izomorfizmu grafów przechodnich wierzchołków. Jest tak, ponieważ dwa wykresy przechodnie wierzchołków są izomorficzne wtedy i tylko wtedy, gdy ich rozłączne połączenie jest przechodnie wierzchołków. Uważam, że złożoność izomorfizmu grafów dla grafów przechodnich werteksów nie jest znana.


W przypadku drugiego pytania znalazłem częściowy wynik. Circulant wykres wykres Cayley na grupie cyklicznej. Evdokimov i Ponomarenko [2] pokazują, że rozpoznawanie wykresów krążeniowych można przeprowadzić w czasie wielomianowym. Również rozdział książkowy Alspacha [1, Rozdział 6: Wykresy Cayleya, Rozdział 6.2: Rozpoznawanie] byłby dla ciebie interesujący, chociaż mówi, że:

Zignorujemy obliczeniowy problem rozpoznawania, czy dowolny wykres jest wykresem Cayleya. Zamiast tego zawsze zakładamy, że wykresy Cayleya zostały opisane w kategoriach grup, na których są zbudowane, wraz z zestawami połączeń. W przypadku większości problemów nie stanowi to wady.


  1. Beineke, Wilson, Cameron. Tematy w teorii grafów algebraicznych . Cambridge University Press, 2004.
  2. Evdokimov, Ponomarenko. Grafy cyrkulacyjne: Rozpoznawanie i testowanie izomorfizmu w czasie wielomianowym. St. Petersburg Math. J. 15 (2004) 813-835. doi: 10.1090 / S1061-0022-04-00833-7
  3. Jajcay, Malnič, Marušič. O liczbie zamkniętych spacerów w grafach przechodnich wierzchołków. Dyskretna matematyka. 307 (2007) 484–493. doi: 10.1016 / j.disc.2005.09.039
Yota Otachi
źródło
4
n1xx