Finding the best subgraph

Question

I am trying to solve the following problem:

Given a connected graph G = (V, E) and a vertex t ∈ V, I need to find a subgraph G'= (V', E ') where t ∈ V'. G' should maximize some objective function and minimize the count of vertexes it contains.

Max f(G')
Min |V'|

In this multi-objective optimization problem, maximize f (G') is more important than minimize the number of vertexes.

Let's check a practical situation with a similar problem:

Suppose that we have to design an ad hoc wireless network in a building where the client devices have a fixed location and there's just one AP connected to the wired network. Initially we put an AP on every room and calculate, using a propagation model, the APs that can be connected and the client devices for which they provide coverage. In this initial distribution probably several APs will provide coverage to the same client device, so we need to optimize it.

Fig 1. Red dot represents the AP connected to the wired network and black dots denote the rest of the APs. Solid lines between APs show us how they are connected.

The graph that form the APs’s connections in the fig 1 represents the connected graph G of our problem and the AP connected to the wired network is the node t. Optimize the graph that represent this initial network design implies to find a subgraph that contains the AP connected to the wired network and maximize the percent of covered client devices (Max f(G') ) minimizing the count of APs (Min |V’|). Like in the problem, maximize the percent of covered client devices is the main target.

Fig 2. A possible solution.

Using brute-force algorithm, it seems like a NP-Completeness problem; find the optimal solution require examining all potential subgraphs (all containing the node t) and proofing a possible solution too. What do you think about?

Answer 1

This is NP-complete. Let f(G') = 1 if G' is a complete graph on k vertices and 0 otherwise. Now this problem is simply finding if G has a clique of size k.