Czy konieczne jest wywołanie mnożenia macierzy

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. $K_{1,3}$ $O(n^4)$ $O(n^{\omega+1})$ $\omega$ $N[v]$ $v$

$o(n^{\omega+1})$ $O(n^c)$ $O(n^{\max{(c,2)}})$ $\Omega(n^\omega)$

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? $O(n^{\omega+1})$

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

Możesz użyć metody znalezienia trójkąta przez Alona i in. W , dla każdego węzła, który kończy się na który jest lepiej niż jeśli wykres nie jest zbyt gęsty.

O (| E |^{1.41})

$O(|E|^{1.41})$

O (| V | \cdot | E |^{1.41})

$O(|V|\cdot |E|^{1.41})$

| V |^{ω + 1}

$|V|^{\omega+1}$

— RB

@RB, dziękuję za zwrócenie na to uwagi. Podstawową ideą jest nadal uruchamianie -tego algorytmu detekcji niezależnie od trójkąta , czego chcę uniknąć.

n

$n$

— Yixin Cao

Jak możemy spodziewać się znalezienia algorytmu niezwiązanego ze znalezieniem trójkąta? Ponieważ niezależnie od algorytmu należy sprawdzać sąsiadów każdego wierzchołka. Mam na myśli, że własność jest własnością lokalną, z wyjątkiem stałej różnicy współczynników każdy wierzchołek powinien być widoczny. (Lub nie wyobrażam sobie żadnego naturalnego algorytmu, który omija tę lokalizację). Czy masz jakiś niejasny pomysł?

— Saeed

Może warto wspomnieć, że jeśli znajdziemy pazur w czasie f (n), możemy również znaleźć trójkąt w czasie f (n + 1) (wystarczy uzupełnić wykres i dodać jeszcze jeden wierzchołek połączony ze wszystkimi ), więc nie powinniśmy mieć nadziei na znalezienie czegoś lepszego niż .

n^{ω}

$n^\omega$

— domotorp

@domotorp, wydaje się, że część jest jasna, na odwrót nie jest jasne, to znaczy, dlaczego potrzebujemy wyszukiwania liniowego. Jak zauważył również Yixin, może istnieć inny algorytm, który nie wykorzystuje algorytmu znajdowania trójkątów i rozwiązuje problem w , co moim zdaniem jest trudne do znalezienia takiego algorytmu i prawdopodobnie jest łatwiejsze aby pokazać, że dowolny algorytm wykorzystuje wyszukiwanie trójkątów jako podprogram (lub może być konwertowany) z liniowym wyszukiwaniem.

o (n^{ω + 1})

$o(n^{\omega +1})$

— Saeed,

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(n^{1+\omega})$

Niech będzie wykresem, na którym chcemy wykryć istnienie pazura. Niech być zestaw (zamówione) pary wierzchołków . Rozważ następującą macierz logiczną o rozmiarze : każdy wiersz jest indeksowany przez niektóre , każda kolumna jest indeksowana przez niektóre , a odpowiedni wpis to jeden wtedy i tylko wtedy, gdy $G=(V,E)$ $A$ $V$ $M$ $|V|\times |A|$ $u\in V$ $(v,w)\in A$ , i . Rozważmy logiczny produkt macierzy i jego transponowaniem . Wykres ma pazur wtedy i tylko wtedy, gdy istnieje tak że wpis w wierszu indeksowanym przez a kolumna indeksowanym przez wynosi jeden. $\{u,v\}\in E$ $\{v,w\}\in E$ $\{u,w\}\notin E$ $M$ $M^T$ $G$ $\{u,v\}\notin E$ $MM^T$ $u$ $v$

Złożoność tego algorytmu jest zasadniczo złożonością obliczania iloczynu logicznego macierzy macierzy , gdzie oznacza liczbę wierzchołków na wykresie. Wiadomo, że taki produkt macierzowy można obliczyć w czasie , który jest lepszy niż dla najlepiej znanej górnej granicy . Oczywiście, jeśli (zgodnie z przypuszczeniami), wówczas dwa podejścia dają tę samą złożoność $n\times n^2$ $n^2\times n$ $n$ $O(n^{3.3})$ $O(n^{1+\omega})$ $\omega$ $\omega=2$ . $O(n^3)$

— Francois Le Gall
źródło

Świetny! Właśnie tego chcę na pierwsze pytanie: tylko jedno wywołanie mnożenia macierzy, choć większe. Zaczekam na więcej komentarzy lub odpowiedzi na moje drugie pytanie, zanim przyjmuję je jako odpowiedź.

— Yixin Cao

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 z $n$

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 gdzie jest stopniem każdego wierzchołka, ponieważ to, czego szukasz, to trójkąt w sąsiedztwo każdego wierzchołka. $n\times n$ $d\times d$ $d$

Po drugie, na wykresie bez pazurów każdy wierzchołek musi mieć $O(\sqrt m)$ $O(\sqrt m)$ $n$

$2m$ $O(\sqrt m)$ $O(\sqrt m)$ $O(m^{(1+\omega)/2})$ $O(nm^{\omega/2})$

— David Eppstein
źródło

Wow, to sprytny pomysł, zastanawiałem się, czy można przeprowadzić wyszukiwanie podliniowe (faktycznie to obalając) i nawet nie pomyślałem o wewnętrznych właściwościach problemu.

— Saeed

Dziękuję David. Przez chwilę zostawiam otwarte, ponieważ moje drugie pytanie wydaje się jeszcze nie zauważone.

— Yixin Cao