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$

ds.algorithms graph-theory graph-algorithms sparse-matrix 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,