Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?

Problem z rowem jest następujący: $k$

Instancja: Niekierowany wykres z wierzchołkami i do krawędzie. $G$ $n$ $n \choose 2$

Pytanie: Czy w istnieje (właściwy) cykl ? $k$ $G$

Tło: Dla każdego ustalonego $k$ możemy rozwiązać cykl $2k$ w czasie $O(n^2)$ .

Raphael Yuster, Uri Zwick: Znalezienie nawet cykli jeszcze szybciej. SIAM J.
Discrete Math. 10 (2): 209–222 (1997)

Nie wiadomo jednak, czy uda nam się rozwiązać 3-cyklowy (tj. 3-klikowy) w czasie krótszym niż mnożenie macierzy.

Moje pytanie: Zakładając, że $G$ nie zawiera 4 cykli, czy możemy rozwiązać problem 3 cykli w czasie $O(n^2)$ ?

David zaproponował podejście do rozwiązania tego wariantu problemu 3-cyklowego w czasie $O(n^{2.111})$ .

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable Michael Wehar
źródło

Wydaje się, że jeśli najmniejszy cykl wykresu ma długość co najmniej 5, to ma co najwyżej krawędzie. Link: link.springer.com/article/10.1007%2FBF01787638

G

$G$

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Michael Wehar

Dodatkowe informacje można znaleźć w tym artykule: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Michael Wehar

Myślę, że może zainteresować Cię także Eisenbrand, Friedrich i Fabrizio Grandoni. „O złożoności kliki o stałym parametrze i dominującego zestawu.” Theoretical Computer Science 326.1 (2004): 57-67. (W przypadku, gdy jeszcze tego nie wiesz).

Juho,

Odpowiedzi:

Tak, to jest znane. Pojawia się w jednym z cytowanych referencji dotyczących znalezienia trójkąta ...

Mianowicie Itai i Rodeh pokazują w SICOMP 1978, jak znaleźć w czasie cykl na wykresie, który ma co najmniej jedną krawędź większą niż cykl długości minimalnej. (Zobacz pierwsze trzy zdania streszczenia tutaj: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) Jest to prosta procedura oparta na właściwościach szerokości pierwszego Szukaj. $O(n^2)$

Zatem jeśli twój wykres jest wolny od 4 cykli i jest trójkąt, jego algorytm musi go wyprowadzić, ponieważ nie może wygenerować 5 lub więcej cykli.

Ryan Williams
źródło

Nie jest kwadratowy, ale Alon Yuster i Zwick („Znajdowanie i zliczanie podanych cykli długości”, Algorytmica 1997) podają algorytm znajdowania trójkątów w czasie , gdzie jest wykładnikiem szybkiego mnożenia macierzy. Do 4 stopnia wolnych wykresach podłączając i (w przeciwnym razie istnieje -cycle niezależnie od istnienia -cycles) daje czas . $O(m^{2\omega/(\omega+1)})$ $\omega$ $\omega<2.373$ $m=O(n^{3/2})$ $4$ $3$ $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$

David Eppstein
źródło

To jest świetne! Bardzo to doceniam. :)

Michael Wehar,

Tak, jeśli wykres nie ma 4 cykli, to ma co najwyżej krawędzie. Link: books.google.com/…

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Michael Wehar

Jeśli się mylę, możesz mnie poprawić. Wygląda na to, że „The Even Circuit Theorem” Erdosa mówi, że jeśli wykres jest wolny od cykl, to ma co najwyżej krawędzie. Link: sciencedirect.com/science/article/pii/S0012365X99901073

2 k

$2k$

O (n^{1 + \frac{1}{k}})

$O(n^{1+\frac{1}{k}})$

Michael Wehar

W rezultacie, jeśli wykres nie ma cyklu 6, to ma co najwyżej krawędzie. Dlatego możemy ustalić, czy ma on 3- czas za pomocą metody, którą zasugerował David. :)

O (n^{\frac{4}{3}})

$O(n^{\frac{4}{3}})$

O (n^{1.876})

$O(n^{1.876})$

Michael Wehar,

Ponadto, dla dowolnego ustalonego , jeśli jest wolne od cyklu, wówczas możemy ustalić, czy ma 3-cykl w czasie subkwadratowym, ponieważ nie ma zbyt wielu krawędzi. Jednak gdy , wtedy rzeczy stają się interesujące. Czy możemy pokonać ?

k > 2

$k > 2$

G

$G$

2 k

$2k$

G

$G$

G

$G$

k = 2

$k = 2$

O (n^{2.111})

$O(n^{2.111})$

Michael Wehar,