寻找最好的子

Question

我试图解决以下问题：

给定一个连通图G =（V，E）和顶点牛逼∈V，我需要找到一个子图G“=（V” ，E'）其中t∈V'。 G'应该最大化一些目标函数并且最小化它包含的顶点数。

Max f(G') 
Min |V'| 

在这个多目标优化问题中，最大化f（G'）比最小化顶点数量更重要。

让我们来看看实际情况类似的问题：

假设我们要设计的建筑物，其中客户端设备有一个固定位置的ad hoc无线网络而且也只是连接到有线网络的一个AP 。最初，我们在每个房间放置AP，并使用传播模型计算可连接的AP以及它们提供覆盖的客户端设备。在这个初始分布中，可能有几个AP将覆盖同一个客户端设备，所以我们需要对其进行优化。

图1红点代表连接到所述有线网络的AP点和黑点分别表示受影响的其余部分。 AP之间的实线向我们展示了它们是如何连接的。

形成图1中AP的连接的图表示我们问题的连通图G，连接到有线网络的AP是节点t。优化代表这种初始网络设计的图表意味着找到一个包含连接到有线网络的AP的子图，并最大化覆盖客户端设备的百分比（Max f（G'）），以最大限度地减少AP的数量（Min | V'| ）。就像问题一样，最大化客户端设备的百分比是主要目标。

图2，一种可能的解决方案。

使用蛮力算法，它似乎是一个NP完全性问题;找到最佳解决方案需要检查所有可能的子图（都包含节点t）并证明可能的解决方案。你有什么想法？

Answer 1

这是NP-complete。令f（G'）= 1如果G'是顶点的完整图形，否则为0。现在这个问题只是发现G有一个大小为k的集团。