Algoritmos para encontrar camarilla en gráfico de grado acotado

Considere una gráfica con $n$ vértices y grado máximo $\Delta$ . Me gustaría saber si el gráfico tiene alguna $s$ camarillas, donde $s \leq \Delta$ y ambas son pequeñas en comparación con $n$ . Solo necesito encontrar una sola camarilla (o certificar que no existe)

Hay una manera directa de hacer esto: para cada vértice $v$ , pruebe todos $s$ subconjuntos de los vecinos de $v$ . El trabajo es por lo tanto $\approx n \binom{\Delta}{s-1}$ .

¿Hay algoritmos más eficientes que este? ¿Incluso lograr una aceleración exponencial sería bueno?

graph-algorithms David Harris
fuente

¿No tienes ?

s \leq Δ

$s\leq\Delta$

Lamine

Una respuesta positiva a esta pregunta implicará que la camarilla se puede resolver en tiempo. Tenga en cuenta que . O, de manera equivalente, considere resolver el problema de la camarilla en para cada vértice .

n^{o (s)}

$n^{o(s)}$

Δ < n

$\Delta<n$

N [v]

$N[v]$

v

$v$

Yixin Cao

@Yixin, ¡me interesaría incluso en soluciones que llevan tiempo, digamos, donde es una constante.

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

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

c < 1

$c < 1$

David Harris

Respuestas:

Eppstein, Löffler, y Strash modificarse el algoritmo de Bron-Kerbosch, la obtención de un algoritmo que enumera todas las camarillas máxima en de tiempo $O(dn 3^{d/3})$ , donde es la degeneración del gráfico (nota ) $d$ $d \le \Delta$

La misma idea puede extenderse para el problema de la camarilla máxima en gráficos degenerados $d$ , y el tiempo de ejecución puede mejorarse a . $O^*(2^{d/4})$

Austin Buchanan
fuente