Algoritma untuk menemukan klik dalam grafik derajat terbatas

Pertimbangkan grafik dengan simpul dan derajat maksimum . Saya ingin menemukan jika grafik mempunyai geng, di mana dan keduanya kecil dibandingkan dengan . Saya hanya perlu menemukan satu klik seperti itu (atau menyatakan tidak ada) $n$ $\Delta$ $s$ $s \leq \Delta$ $n$

Ada cara mudah untuk melakukan ini: untuk setiap simpul , uji semua subset dari tetangga . karyanya . $v$ $s$ $v$ $\approx n \binom{\Delta}{s-1}$

Apakah ada algoritma yang lebih efisien dari ini? Bahkan mencapai kecepatan eksponensial akan bagus?

graph-algorithms David Harris
sumber

Apakah kamu tidak punya

s \leq Δ

$s\leq\Delta$ ?

Lamine

Jawaban positif untuk pertanyaan ini akan menyiratkan klik dapat diselesaikan dalam waktu

n^{o (s)}

$n^{o(s)}$ waktu. Perhatikan bahwa

Δ < n

$\Delta<n$ . Atau yang setara, pertimbangkan untuk menyelesaikan masalah klik dalam

N [v]

$N[v]$ untuk setiap simpul

v

$v$ .

Yixin Cao

@Yixin, saya akan tertarik bahkan pada solusi yang membutuhkan waktu katakanlah

n Δ^{c (s - 1)} / (s - 1)!

$n \Delta^{c(s-1)}/(s-1)!$ , di mana

c < 1

$c < 1$ adalah konstanta.

David Harris

Jawaban:

Eppstein, Löffler, dan Strash memodifikasi algoritma Bron-Kerbosch, memperoleh algoritma yang mencantumkan semua klik maksimal dalam waktu waktu $O(dn 3^{d/3})$ , di mana adalah degenerasi grafik (catatan ). $d$ $d \le \Delta$

Gagasan yang sama dapat diperluas untuk masalah klik maksimum dalam grafik -degenerate $d$ , dan runtime dapat ditingkatkan menjadi . $O^*(2^{d/4})$

Austin Buchanan
sumber