在解决方案中对预定顶点的K-Clique问题的复杂性是什么？

Question

clique（来自维基百科）：

clique是一个无向图的顶点的子集，使得每一个 Clique中的两个不同的顶点是邻近的;也就是说，它的诱发 子图已完成。

k-clique问题：找到大小的clique。这是根据wiki的np-cheed，

Cliques还研究了计算机科学中的研究：发现图表中的给定尺寸是否存在于图形（Clique问题）是NP完整的，但尽管这种硬度结果已经研究了许多用于查找派系的算法。

让我们考虑一个“受限的K-Clique问题” - 这是一个K-Clique问题，其限制包括在解决方案中的预定顶点。这个问题的复杂性是什么？是文学中的已知问题吗？

Answer 1

仍然是 $ \ mathsf {np} $ -complete。 考虑来自普通 $ \ mathrm {clique} $ 问题的以下减少： 给定图 $ g $ 和一些所需的clique size $ k $ ，添加一个新的顶点 $ v ^ \ ast $ 连接到 $ g $ 的所有顶点，以获取新图 $ g ^ \ ast $ 。 然后 $（g ^ \ ist，k + 1，v ^ \ ist）$ 是修改后的yes-instance$ \ mathrm {clique} $ 问题如果 $（g，k）$ 是 $ \ mathrm {clique} $ 。