使用最大数量的边缘找到给定尺寸的连接子图，其中包括给定的顶点

Question

考虑一个无向图 $ g= [v，e] $ 。让 $ v $ 是顶点集： $ v= {v_1，..，v_n \} $ 和 $ e $ 是一组边缘。让 $ c $ 是包含顶点 $ v_1 $ 的连接组件。我想在 $ c $ 中的所有连接的子图中，找到连接的子图（不确定这个术语）最大的边缘。满足以下内容：

1. 包括顶点 $ v_1 $
2. 完全是 $ m $ 顶点数（包括 $ v_1 $ ）

通过 $ c $ ，表示 $ c $ 的子图，这样它中的每对顶点都通过路径连接。

Answer 1

它是NP - 硬（通过从Clique问题减少）。

let $ g $ 是一个任意图形，我们希望检查是否存在大小的clique $ m-1 $ 在此图中。这个问题是np-clyp。通过添加 $ v_1 $ 将其连接到 $ g $ 中的所有顶点，我们减少了对您的问题的集团问题（因为Clique，当存在时，具有最大边缘数）。