Algoritmos para encontrar clique em gráfico de graus delimitados

Considere um gráfico com vértices e o grau máximo . Eu gostaria de saber se o gráfico tem nenhum panelinhas, onde e ambos são pequenos em comparação com . Eu só preciso encontrar um único clique (ou certificar que não existe) $n$ $\Delta$ $s$ $s \leq \Delta$ $n$

Existe uma maneira simples de fazer isso: para cada vértice , teste todos os conjuntos dos vizinhos de . O trabalho é, portanto, . $v$ $s$ $v$ $\approx n \binom{\Delta}{s-1}$

Existem algoritmos mais eficientes do que isso? Mesmo alcançar uma aceleração exponencial seria bom?

graph-algorithms David Harris
fonte

Você não tem

s \leq Δ

$s\leq\Delta$ ?

Lamine

Uma resposta positiva a esta pergunta implicará que o clique pode ser resolvido em tempo. Observe que . Ou equivalente, considere resolver o problema de clique em para cada vértice .

n^{o (s)}

$n^{o(s)}$

Δ < n

$\Delta<n$

N [v]

$N[v]$

v

$v$

Yixin Cao

@ Yixin, eu estaria interessado mesmo em soluções que levam tempo digam, onde é uma constante.

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

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

c < 1

$c < 1$

David Harris

Respostas:

Eppstein, Lfler, e Strash modificada do algoritmo Bron-Kerbosch, obtendo-se um algoritmo que lista todos os cliques maximais em de tempo $O(dn 3^{d/3})$ , em que é a degeneração do gráfico (nota ) $d$ $d \le \Delta$

A mesma idéia pode ser estendida para o problema máximo de clique em gráficos com degeneração $d$ e o tempo de execução pode ser aprimorado para . $O^*(2^{d/4})$

Austin Buchanan
fonte