Поиск лучшего подграфа

Я пытаюсь решить следующую проблему:

Для данного связного графа G = (V, E) и вершины t ∈ V мне нужно найти подграф G'= (V', E'), где t ∈ V'. G' должен максимизировать некоторую целевую функцию и минимизировать количество содержащихся в ней вершин.

Max f(G')
Min |V'|

В этой многокритериальной задаче оптимизации максимизация f(G') более важна, чем минимизация количества вершин.

Проверим практическую ситуацию с похожей задачей:

Предположим, что нам нужно спроектировать одноранговую беспроводную сеть в здании, где клиентские устройства имеют фиксированное местоположение, а к проводной сети подключена только одна точка доступа. Сначала мы устанавливаем точку доступа в каждой комнате и вычисляем, используя модель распространения, точки доступа, которые можно подключить, и клиентские устройства, для которых они обеспечивают покрытие. В этом первоначальном распределении, вероятно, несколько точек доступа будут обеспечивать покрытие для одного и того же клиентского устройства, поэтому нам необходимо его оптимизировать.

Рис. 1. Красная точка обозначает точку доступа, подключенную к проводной сети, а черные точки обозначают остальные точки доступа. Сплошные линии между точками доступа показывают нам, как они связаны.

Граф, который формирует соединения точек доступа на рис. 1, представляет связный граф G нашей задачи, а точка доступа, подключенная к проводной сети, является узлом t. Оптимизация графа, представляющего этот первоначальный проект сети, подразумевает поиск подграфа, содержащего точку доступа, подключенную к проводной сети, и максимизацию процента охваченных клиентских устройств (Max f(G')), сводя к минимуму количество точек доступа (Min |V'| ). Как и в задаче, главной целью является максимизация процента охваченных клиентских устройств.

Рис 2. Возможное решение.

Используя алгоритм грубой силы, это похоже на проблему NP-полноты; поиск оптимального решения требует изучения всех потенциальных подграфов (все они содержат узел t) и проверки возможного решения. О чем вы думаете?