¿Cuál es la complejidad del problema de K-Clique con un vértice predeterminado en la solución?

Question

clique (de Wikipedia):

clique es un subconjunto de vértices de un gráfico no dirigido de modo que cada Dos vértices distintos en la camarilla son adyacentes;es decir, su indujo subgrógrafo está completo.

K-Clique PROBLEMA: Encontrar una CLÍA DE TAMAÑO K. Esto es NP: completo de acuerdo con Wiki,

Las camarillas también se han estudiado en la informática: encontrar si hay una camarilla de un tamaño determinado en un gráfico (el problema de la clama) es NP-completa, pero a pesar de este resultado de dureza, se han estudiado muchos algoritmos para encontrar camaras.

Consideremos un "problema de k-clique restringido", que es un problema de k-clique con una restricción de tener un vértice predeterminado incluido en la solución.¿Cuál sería la complejidad de este problema?¿Es un problema conocido en la literatura?

Answer 1

Todavía es $ \ mathsf {np} $ -clete. Considere la siguiente reducción del $ \ mathrm {clique} $ problema: Dado un gráfico $ G $ y algunos camisones deseados Tamaño $ k $ , agregue una nueva clase de vértice $ V ^ \ AST $ que está conectado a todos los vértices de $ g $ para obtener un nuevo gráfico $ g ^ \ as $ . Luego $ (g ^ \ ast, k + 1, v ^ \ ast) $ es una instancia de Sí, de su $ \ mathrm {clique} $ problema si y solo si $ (g, k) $ es un sí-instancia de $ \ mathrm {clique} $ .