Qual é a complexidade do problema do K-Clique com um vértice predeterminado na solução?

Question

Clique (da Wikipedia):

.

clique é um subconjunto de vértices de um gráfico não direcionado de modo que todos Dois vértices distintos no clique são adjacentes;isto é, sua induzida Subgráfico está completo.

K-Clique Problema: Encontrar um clique de tamanho K. Isso é NP-completo de acordo com o Wiki,

.

cliques também foram estudados em ciência da computação: achando se há um clique de um determinado tamanho em um gráfico (o problema de clique) é NP-completo, mas apesar desse resultado de dureza muitos algoritmos para encontrar cliques foram estudados. .

Vamos considerar um "problema de clique restrito" - que é um problema de clique K com uma restrição de ter um vértice predeterminado incluído na solução.Qual seria a complexidade desse problema?É um problema conhecido na literatura?

Answer 1

Ainda é $ \ mathsf {np} $ -complete. Considere a seguinte redução da $ \ mathrm {clique} $ problema: Dado um gráfico $ g $ e algum tamanho de clique desejado $ K $ , adicione uma nova classe $ v ^ \ AST $ que é conectado a todos os vértices da $ g $ para obter um novo gráfico $ g ^ \ AST $ . Em seguida, $ (G ^ \ AST, K + 1, v ^ \ AST) $ é uma instância sim de sua $ \ mathrm {clique} $ problema se e somente se $ (g, k) $ é uma instância sim de matemática $ \ mathrm {clique} $ .