¿Cuál es un buen algoritmo para encontrar el número de camarilla de un vértice de un grafo?

Question

En esta pregunta, "grafo" significa un grafo simple no orientado, sin bucles y sin etiquetas en las aristas o vértices.

Una camarilla en un gráfico $G$ es un subgrafo completo de $G$ . El número de camarilla $\omega_v(G)$ de un vértice $v$ de $G$ es el máximo del orden (=número de vértices) de todas las camarillas de $G$ que contiene $v$ .

¿Existe un buen algoritmo que calcule el número de clique de un vector $v$ en un gráfico?

Los grafos que considero están representados por su matriz de adyacencia, pero un algoritmo que funcione con la lista de aristas de un grafo también estaría bien.

Sé que el número de camarilla $\omega$ de $G$ es el máximo del orden sobre todas las camarillas en $G$ . Por lo tanto, $\omega_v(G)=\omega(N(v))$ , donde $N(v)$ es la vecindad de $v$ ( $v$ incluido). Además, el número de camarilla de un gráfico es el número de independencia de su complemento. Pero no estoy seguro de si esta información es útil o no.

Answer 1

Probablemente ya te hayas dado cuenta de que este problema es NP-duro: si pudieras resolver este problema, entonces podrías encontrar el número de camarilla de un grafo $G$ añadiendo simplemente un vértice $v$ a $G$ y conectándolo a todos los vértices previamente existentes de $G$ y, por último, consultar lo que $\omega_v(G \cup v)$ es. El número de camarilla de $G$ sería entonces $\omega(G \cup v) - 1$ .

Esto da lugar a una bonita heurística (aunque puede seguir siendo muy lenta). En primer lugar, se puede considerar el subgrafo inducido (llamémoslo $H$ ) de $G$ en los vértices $v \cup N(v)$ donde $N(v)$ son los vecinos de $v$ . Entonces se podría encontrar una camarilla máxima $C$ para $H \setminus v$ en $O\left(3^{|V(H)| / 3}\right)$ tiempo. Dado que todos los vértices de $H \setminus v$ se garantiza la conexión con $V$ se deduce que $C \cup v$ sería una camarilla máxima en $H$ (y posteriormente) una camarilla máxima en $G$ que contiene $v$ .

Dado que los algoritmos más rápidos de búsqueda de cliques que conocemos se ejecutan en $O\left(3^{V / 3}\right)$ tiempo, la equivalencia de su problema con el problema de la camarilla máxima sugeriría que el mejor algoritmo conocido para su problema también se ejecuta en $O\left(3^{V / 3}\right)$ tiempo. De lo contrario, simplemente habríamos encontrado un algoritmo más rápido para resolver el problema de la camarilla máxima, a través de la reducción que he esbozado en el primer párrafo.