# Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem is to find a subgraph with R vertices that is connected and maximizes the sum of the weights (or values) of the R vertices.

CMCG Problem: The CMCG problem is the MCG problem with a constraint of having one predetermined (fixed) vertex included in the solution.

In 1 it has been stated (First paragraph, Section 1) that MCG is an NP-complete problem, which is proved in [3] (However I could not find the technical report [3] anywhere on the internet).

In 2 it has been "claimed" that CMCG is NP-complete (second to last paragraph, Section 3). But did not provide any proof.

I want to know (and see a proof, if possible) that if CMCG is NP-complete.

In 1 it has been shown that Steiner tree problem, which is NP-complete is a special case of the CMCG problem. Does it imply that CMCG is NP-complete?

[3]:Lee, H. F., and D. R. Dooly. The maximum-weight connected graph problem. Technical Report 93-4, Industrial Engineering, Southern Illinois University, 1993.

## 1 Answer

Firstly, note that you can reduce $$CMCG$$ to $$MCG$$ by setting the value of the node that must be in the set to the sum of all positive weights of all other nodes $$+1$$ and then applying $$MCG$$ and retrieving the result set. Thus $$CMCG\in NP$$.

As proved in the paper the $$NP$$-complete Steiner-Tree problem can be reduced to $$CMCG$$ meaning that $$CMCG$$ is $$NP$$-hard. If a problem is in $$NP$$ and $$NP$$-hard it is by definition $$NP$$-complete.

Hope this helps.