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

25

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.)KK=K11

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ą?

Max
źródło

Odpowiedzi:

15

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. )ΓΓ0ΓΓ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Γ0GGΓGΓ

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 ) .GnmO(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.Γ0

O(mlogn)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.

nn

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.
András Salamon
źródło
Przyjąłem @ czyjąś odpowiedź, ale dziękuję za dodatkowe informacje.
Maks.
12

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.

Yota Otachi
źródło