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

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?$G$$n$$n$$G$

Przypomnij sobie, że wykres jest przechodni na wierzchołki, jeśli działa tranzytowo na$G$$\mathrm{Aut}(G)$$V(G).$

Nie jestem pewien, czy powyższa definicja dopuszcza algorytm wielomianowy, ponieważ może być tak, że kolejność jest wykładnicza.$\mathrm{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$

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 Γ .$\Gamma$$\Gamma$$\Gamma$

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łek$n−1$$G$$G'$$n+1$$u \in V(G)$$v \in V(G')$$G$$G'$$u$$v$ i sprawdzenie, czy istnieją automorfizmy mapujące x na wszystkie pozostałe wierzchołki.$x$$x$

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