I am trying to prove the computer complexity of this optimization problem:
Given a connected graph G = (V, E) and a set S ⊊ V. Find a connected subgraph G'= (V', E ') that:
Min f(G')
Min |V'|
subjet to:
S ⊊ V’
V’ ⊆ V
It looks like a generalization of the minimum spanning tree problem when not all vertexes have to be included in the tree. Is there a known problem that can be used to proof the complexity of this problem by reduction?
Your problem formulation is not saying what you're optimizing on-- f(G') first and within that Min|V'|, or the other way round, or the two combined in some way.
if you optimize on the cost edges, it is the Steiner minimal tree (SMT) problem as is and NP-complete. if you optimize on |V'|, you can reduce SMT to it in polynomial time with the following:
Let edge (u,v) between nodes u and v have cost k. Replace this edge by the following path:
(u, i_1), (i_1, i_2), ..., (i_k, v)
so that the cost of each edge on this path is 1. You replaced the edge of cost (u, v) with a path with k-1 intermediary nodes on it and every edge has cost 1.
Do this for every edge on graph. It reduces SMT to your problem and proves that yours optimizing on |V'| is NP-complete. Your reduction takes
O(C*|V|^2)
time where C is an upper bound on the cost of edges in graph.
Just saw the problem. Hope it helps.