Diberikan grafik bebas 4 siklus , dapatkah kita menentukan apakah grafiknya memiliki 3 siklus dalam waktu kuadratik?

Masalah cycle adalah sebagai berikut: $k$

Instance: Grafik tidak berarah dengan simpul dan hingga sisi. $G$ $n$ $n \choose 2$

Pertanyaan: Apakah ada $k$ siklus) di $G$ ?

Latar Belakang: Untuk setiap diperbaiki $k$ , kita dapat menyelesaikan $2k$ cycle dalam waktu $O(n^2)$ .

Raphael Yuster, Uri Zwick: Menemukan Even Cycles Even Faster. SIAM J.
Discrete Math. 10 (2): 209-222 (1997)

Namun, tidak diketahui apakah kita dapat menyelesaikan 3-siklus (yaitu 3-klik) dalam waktu penggandaan matriks kurang dari.

Pertanyaan Saya: Dengan asumsi bahwa tidak mengandung 4 siklus, dapatkah kita menyelesaikan masalah 3 siklus dalam waktu ? $G$ $O(n^2)$

David menyarankan pendekatan untuk menyelesaikan varian masalah 3-siklus ini dalam waktu . $O(n^{2.111})$

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable Michael Wehar
sumber

Tampaknya jika graf siklus terkecil memiliki panjang setidaknya 5, maka ia memiliki paling banyak edge. Tautan: link.springer.com/article/10.1007%2FBF01787638

G

$G$

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

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

Michael Wehar

Info tambahan dapat ditemukan dalam makalah ini: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Michael Wehar

Saya pikir Anda mungkin juga tertarik pada Eisenbrand, Friedrich, dan Fabrizio Grandoni. "Pada kompleksitas klik parameter tetap dan set yang mendominasi." Ilmu Komputer Teoritis 326.1 (2004): 57-67. (Jika Anda belum menyadarinya).

Juho

Jawaban:

Ya, ini diketahui. Itu muncul di salah satu referensi yang harus dikutip tentang penemuan segitiga ...

Yaitu, Itai dan Rodeh menunjukkan dalam SICOMP 1978 bagaimana menemukan, dalam waktu , sebuah siklus dalam grafik yang paling banyak memiliki satu sisi lebih dari siklus panjang minimum. (Lihat tiga kalimat pertama dari abstrak di sini: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) Ini adalah prosedur sederhana berdasarkan pada properti dari luasnya-pertama Cari. $O(n^2)$

Jadi, jika grafik Anda 4-siklus gratis dan ada segitiga, algoritme mereka harus menampilkannya, karena tidak dapat menampilkan 5 siklus atau lebih besar.

Ryan Williams
sumber

Ini bukan kuadrat, tapi Alon Yuster dan Zwick ( "Mencari dan terus bertambah mengingat siklus panjang", Algorithmica 1997) memberikan algoritma untuk menemukan segitiga dalam waktu , di mana adalah eksponen untuk cepat perkalian matriks. Untuk grafik 4-siklus-bebas, plugging di dan (yang lain ada -siklus terlepas dari keberadaan -cycles) memberikan waktu $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
sumber

Ini bagus! Saya sangat menghargai itu. :)

Michael Wehar

Yap, jika grafik tidak memiliki 4 siklus, maka ia memiliki paling banyak

tepi. Tautan:books.google.com/...

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

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

Michael Wehar

Jangan ragu untuk mengoreksi saya jika saya salah. Tampaknya "The Even Circuit Theorem" oleh Erdos mengatakan bahwa jika sebuah grafik

bebas siklus, maka ia memiliki paling banyak

2 k

$2k$

tepian. Tautan:sciencedirect.com/science/article/pii/S0012365X99901073

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

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

Michael Wehar

Akibatnya, jika grafik tidak memiliki siklus 6, maka ia memiliki paling banyak

tepi. Oleh karena itu, kita dapat menentukan apakah ia memiliki 3 siklus dalam waktu

menggunakan metode yang disarankan David. :)

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

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

O (n^{1.876})

$O(n^{1.876})$

Michael Wehar

Selanjutnya, untuk setiap tetap

, jika

adalah

-siklus bebas, maka kita dapat menentukan apakah

memiliki 3-siklus dalam waktu subquadratic karena

tidak memiliki terlalu banyak tepi. Namun, ketika

, saat itulah hal menjadi menarik. Bisakah kita mengalahkan

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 615