2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.