Algorithmen zum Auffinden von Cliquen in einem Graphen mit begrenztem Grad

Betrachten Sie einen Graphen mit Eckpunkten und maximalem Grad . Ich würde gerne herausfinden, ob der Graph Cliquen hat, wobei und beide im Vergleich zu klein sind . Ich muss nur eine einzige solche Clique finden (oder bestätigen, dass es keine gibt) $n$ $\Delta$ $s$ $s \leq \Delta$ $n$

Es gibt einen einfachen Weg, dies zu tun: Testen Sie für jeden Scheitelpunkt alle Teilmengen der Nachbarn von . Die Arbeit ist also $v$ $s$ $v$ . $\approx n \binom{\Delta}{s-1}$

Gibt es effizientere Algorithmen als diese? Selbst eine exponentielle Beschleunigung wäre gut?

graph-algorithms David Harris
quelle

Hast du nicht

s \leq Δ

$s\leq\Delta$

Lamine

Eine positive Antwort auf diese Frage impliziert Clique in gelöst werden kann ,

Zeit. Man beachte, dass

. Oder betrachten Sie gleichwertig das Cliquenproblem in

für jeden Scheitelpunkt

n^{o (s)}

$n^{o(s)}$

Δ < n

$\Delta<n$

N [v]

$N[v]$

v

$v$

Yixin Cao

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

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

c < 1

$c < 1$

Antworten:

$O(dn 3^{d/3})$ $d$ $d \le \Delta$

$d$ $O^*(2^{d/4})$

Austin Buchanan
quelle