Złożoność „jest wykresem produkt”

To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie.

Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność ustalenia, czy wykres jest izomorficzny w stosunku do nietrywialnego produktu? (Z pewnością dla iloczynu kartezjańskiego K = K ◻ 1, gdzie 1 jest wykresem z jednym wierzchołkiem.)$K$$K = K \square 1$$1$

Przejrzałem strony „wykres czynników” i „rozkład współczynników wykresów” na Wikipedii, ale żadne z nich nie wydaje się powiązane. Czy ten problem jest znany pod inną nazwą?

Sprawdź artykuł Wilfried, Imrich; Iztok, Peterin, Rozpoznawanie produktów kartezjańskich w czasie liniowym . Discrete Math., 307, 3-5, Strony: 472--483, 2007. Myślę, że Imrich ma więcej dokumentów na inne produkty.

Kilka produktów grafowych można rozpoznać w czasie wielomianowym. Jak zwykle produkt kartezjański jest najłatwiejszy, a przypadek kartezjański jest również podstawą algorytmów dla kilku innych produktów. Rozpoznanie produktu leksykograficznego (składu) jest równoważne z izomorfizmem grafowym.

Bardziej szczegółowo:

Niech będzie klasą skończonych prostych grafów, a Γ 0 będzie klasą skończonych prostych grafów, które mogą mieć pętle własne. (Wyraźnie Γ ⊂ Γ 0. )$\Gamma$$\Gamma_0$$\Gamma \subset \Gamma_0$

Decyzję, czy podłączony wykres wejściowy ma czynniki w Γ 0, można podjąć w czasie wielomianowym dla produktów kartezjańskich i silnych, a także dla produktu bezpośredniego, gdy G nie jest dwustronna. Decyzja o tym, czy G ma czynniki w Γ, jest w czasie wielomianowym dla produktu kartezjańskiego, ale jest mało prawdopodobne, że będzie w czasie wielomianowym dla produktu leksykograficznego. Nie znam statusu decydowania, czy G ma czynniki Γ dla bezpośrednich i mocnych produktów.$G$$\Gamma_0$$G$$G$$\Gamma$$G$$\Gamma$

Odpowiednie wyniki Imricha i Klavžara:

Twierdzenie 4.10. Dla połączonego wykresu na n wierzchołkach i krawędziach m można znaleźć pierwszą faktoryzację względem iloczynu kartezjańskiego w czasie O ( m n ) z wykorzystaniem przestrzeni O ( m ) .$G$$n$$m$$O(mn)$$O(m)$

Twierdzenie 5.43. Rozkład pierwszorzędowych połączonych grafów dwudzielnych w w odniesieniu do produktu bezpośredniego i połączonych prostych grafów w odniesieniu do produktu silnego można określić w czasie wielomianowym.$\Gamma_0$

$O(m\log n)$$O(m)$

W przypadku produktu leksykograficznego:

Twierdzenie 6.20. Problem decyzyjny, czy dany połączony wykres jest liczbą pierwszą w odniesieniu do produktu leksykograficznego, jest co najmniej tak trudny jak problem izomorfizmu grafu.

$n$$n$

Tak więc podjęcie decyzji, czy wykres jest liczbą pierwszą w odniesieniu do produktu leksykograficznego, jest równoważne z izomorfizmem graficznym w odniesieniu do redukcji Turinga.

Przypadek bezpośredniego i silnego produktu z czynnikami bez pętli wydaje się być nieobecny w referencjach, na które patrzyłem. Byłbym wdzięczny za wszelkie wskazówki do artykułów omawiających tę sprawę lub wskazówkę, dlaczego jest to nieciekawe.

• Wilfried Imrich i Sandi Klavžar, Wykresy produktów: struktura i rozpoznawanie . Wiley, 2000. ISBN 0-471-37039-8.

Istnieje algorytm czasu liniowego do określania czynników pierwotnych połączonych wykresów w odniesieniu do iloczynu kartezjańskiego. Zobacz artykuł Imricha i Peterina.