Pazur to . Trywialny algorytm wykryje pazur w czasie . Można to zrobić w , gdzie jest wykładnikiem szybkiego mnożenia macierzy, w następujący sposób: weź podrozdział wywołany przez dla każdego wierzchołka i znajdź trójkąt w jego uzupełnienie. O ( n 4 ) O ( n ω + 1 ) ω N [ v ] v
Pytanie:
- Czy jest w tym jakiś postęp? Czy jakikolwiek postęp w pokazaniu, że jest to niemożliwe?
- Czy są inne naturalne problemy z algorytmami czasu , które są najlepsze?
Uwaga:
- Bezpośrednio proszę o wykrycie pazura zamiast rozpoznawania grafów bez pazurów. Chociaż algorytm zwykle rozwiązuje oba, istnieje kilka wyjątków.
- W Podręczniku algorytmów i informatyki teoretycznej twierdzi się, że można go znaleźć w czasie liniowym, ale była to tylko literówka (patrz „wydajne reprezentacje grafów”).
graph-theory
graph-algorithms
graph-classes
Yixin Cao
źródło
źródło
Odpowiedzi:
Myślę, że możemy zrobić nieco lepiej niż przypadku gęstych grafów, stosując mnożenie macierzy prostokątnej. Podobny pomysł zastosowali Eisenbrand i Grandoni („O złożoności kliki o ustalonych parametrach i dominującym zbiorze”, Theoretical Computer Science tom 326 (2004) 57–67) do wykrywania 4-kliki.O(n1+ω)
Niech będzie wykresem, na którym chcemy wykryć istnienie pazura. Niech być zestaw (zamówione) pary wierzchołków V . Rozważ następującą macierz logiczną M o rozmiarze | V | × | A | : każdy wiersz jest indeksowany przez niektóre u ∈ V , każda kolumna jest indeksowana przez niektóre ( v , w ) ∈ A , a odpowiedni wpis to jeden wtedy i tylko wtedy, gdy { u , v } ∈G=(V,E) A V M |V|×|A| u∈V (v,w)∈A , { V , W } ∈ E i { U , W } ∉ E . Rozważmy logiczny produkt macierzy M i jego transponowaniem M T . Wykres G ma pazur wtedy i tylko wtedy, gdy istnieje { u , v } ∉ E,
tak że wpis M M T w wierszu indeksowanym przez u, a kolumna indeksowanym przez v wynosi jeden.{u,v}∈E {v,w}∈E {u,w}∉E M MT G {u,v}∉E MMT u v
Złożoność tego algorytmu jest zasadniczo złożonością obliczania iloczynu logicznego macierzy macierzy n 2 × n , gdzie n oznacza liczbę wierzchołków na wykresie. Wiadomo, że taki produkt macierzowy można obliczyć w czasie O ( n 3,3 ) , który jest lepszy niż O ( n 1 + ω ) dla najlepiej znanej górnej granicy ω . Oczywiście, jeśli ω = 2 (zgodnie z przypuszczeniami), wówczas dwa podejścia dają tę samą złożoność On×n2 n2×n n O(n3.3) O(n1+ω) ω ω=2 .O(n3)
źródło
Nie wiem, jak uniknąć robi mnożenia macierzy, ale można analizować je w taki sposób, że czas to skutecznie, że z mniejszej liczby z nich. Ta sztuczka pochodzi zn
Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), „Skuteczne znajdowanie i liczenie małych indukowanych subgrafów”, Information Processing Letters 74 (3–4): 115–121, doi: 10.1016 / S0020-0190 (00) 00047-8, MR 1761552.
Pierwszą obserwacją jest to, że gdy idziesz do mnożenia macierzy, macierze tak naprawdę nie są , ale d × d, gdzie d jest stopniem każdego wierzchołka, ponieważ to, czego szukasz, to trójkąt w sąsiedztwo każdego wierzchołka.n×n d×d d
Po drugie, na wykresie bez pazurów każdy wierzchołek musi miećO(m−−√) O(m−−√) n
źródło