Skuteczne znajdowanie 5-cykli na rzadkim wykresie.

(crossposted z MathOverflow)

Cześć,

Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length

Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo w analizie złożoności. $m$ $n$

Czy w takim przypadku możemy zrobić coś lepszego niż kodowanie kolorami w celu znalezienia 5-cykli? Pozwól, że podam konkretne sformułowanie mojego pytania:

Jaka jest minimalna wartość , aby istniał algorytm czasu do wykrywania cyklu o długości 5? Co to jest algorytm? A co to jest jeśli zabronisz niepraktycznych metod, takich jak szybkie mnożenie macierzy Coppersmitha-Winograda? $\alpha$ $O(m^\alpha)$ $\alpha$

— Andrew D. King
źródło

Crosspost z MO.

— Hsien-Chih Chang 之之

Czy twoje wykresy mają inną strukturę niż rzadka? (Takich jak na przykład niska degeneracja).

— Robin Kothari,

Nie, możesz ustawić wykres tak diabelski, jak chcesz. Właściwie nie dbam nawet o to, czy wykres jest rzadki: rozważam wykres liniowy , a leżący u jego podstaw wykres taki, że (możemy założyć, że jest prosty). Powód, dla którego traktujęito samo, że wiemi chcę przeanalizować złożoność pod względemi, ale nie mogę nic powiedzieć o tym, jakporównuje do.

G

$G$

H

$H$

G = L (H)

$G=L(H)$

H

$H$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

| E (H) | = | V (G) |

$|E(H)|=|V(G)|$

| V (G) |

$|V(G)|$

| E (G) |

$|E(G)|$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

— Andrew D. King,

Żeby było jasne, nie masz nic przeciwko, jeśli cykl zawiera powtarzające się wierzchołki, prawda?

— user834,

Nie zezwalam na powtarzające się wierzchołki, ale dla 5 cykli nie ma to znaczenia, ponieważ zakładam, że wykres jest prosty i dlatego nie ma 2 cykli.

— Andrew D. King,

Odpowiedzi:

Aby dodać do odpowiedzi Mihai:

Rzeczywiście, 5-cykli (i ogólnie rowe) na rzadkich wykresach można rozwiązać znacznie szybciej niż czas przy użyciu sztuczki wysokiego / niskiego stopnia. Wystarczy spojrzeć na inny artykuł Alona, Yustera i Zwicka: $k$ $O(mn)$

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

Na przykład 5-cykl można znaleźć w czasie , bez żadnej zależności od mnożenia macierzy. Zobacz twierdzenie 3.4 powyższego powiązanego dokumentu. $O(m^{1.67})$

Ponadto, chociaż nie jest zbyt trudno zredukować wykrywanie 5-cyklowe do mnożenia macierzy boolowskiej (ze stałym narzutem czynnika), zmniejszenie w kierunku przeciwnym nie pojawia się na papierze do kodowania kolorami. Ścisła redukcja (która zachowuje złożoność środowiska wykonawczego) od mnożenia macierzy boolowskich do detekcji 5-cyklowej nie jest znana.

— Ryan Williams
źródło

Gęsty przypadek jest zasadniczo równoważny mnożeniu macierzy boolowskiej przez kodowanie kolorami. Zobacz http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.103.5167&rep=rep1&type=pdf .

Dla rzadkich wykresów istnieje algorytm z czasem ze względu na [B. Monien, Jak efektywnie znajdować długie ścieżki, Ann. Discrete Math., 25 (1985), s. 239–254]. Podejrzewam, że coś lepszego mogłoby być możliwe dzięki sztuczkom wysokiego / niskiego stopnia. $O(mn)$

— Mihai
źródło

Dziękuję Ci! Przyjrzę się artykułowi Monien, kiedy będę mógł uzyskać do niego dostęp.

— Andrew D. King,