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?
Przypomnij sobie, że wykres jest przechodni na wierzchołki, jeśli działa tranzytowo na
Nie jestem pewien, czy powyższa definicja dopuszcza algorytm wielomianowy, ponieważ może być tak, że kolejność jest wykładnicza.
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?
Odpowiedzi:
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:
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łekn−1 G G′ n+1 u∈V(G) v∈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:
źródło