I want to proof that the MWCS is an NP-hard problem by proofing that its decision version is NP-Complete. Below I have my proof so far and I hope people can give comments whether it can be formulated better. The MWCS problem (in my case) is defined as follows:
Given a graph $G = (V,E)$ with vertex weights $w(v)$ and a positive integer $k$, find a connected subgraph $(V',E')$ with $|V'| \leq k$ such that $\sum_{v \in V'} w(v)$ is maximized.
The decision version is then given by:
Given a graph $G = (V,E)$ with binary vertex weights $w(v)$ and positive integers $k$ and $r$, is there a connected subgraph $(V',E')$ with $|V'| \leq k$ and $w(V')\geq r$ ?
Now we want to proof the following theorem: The decision version of the $MWCS$ problem is NP-complete, even if the vertex weights are restricted to be binary: $w(v) \in \{0,1\}$ $\forall v \in V$.
Proof For this proof we will use the decision version of the Steiner $l$-Tree $(ST(l))$ problem, which is defined as follows:
Given a graph $G' = (V,E)$, $R \subseteq V$, an integer $l \geq |R|$, is there a steiner tree $T=(V', E')$ in $G$ that spans R with $|V'| \leq l$ ?
To reduce this problem to the decision version of the $MWCS$ problem, we introduce the mapping $f:I_{ST(l)} \rightarrow I_{MWCS}$ that maps every instance of the Steiner $l$-Tree to an instance of the $MWCS$. If we can proof that this mapping maps every yes-instance of $I_{ST(l)}$ to a yes-instance of $I_{MWCS}$ and idem dito for every no-instance, then we have found a reduction from $ST(l)$ to $MWCS$. The mapping $f$ is as follows:
Create a node-weighted graph $G=(V,E)$ with vertex $ w(v) = \begin{cases} 1 & \forall v \in R\\ 0 & \forall v \in V \setminus R \end{cases} $
Set $k=l$ and $|R|=r$
Consider a yes-instance of $I_{ST(l)}$: A Steiner tree $T$ of $q$ vertices ($q \leq l$) and $q-1$ edges (since $T$ is a tree) which spans all vertices of $R$. Then in $G=(V,E)$ this tree $T$ contains less or equal then $k$ vertices and contains $w(T) \geq r$ since all vertices with $w(v)=1$ are contained in T by construction. Since a tree is a connected subgraph, $T$ is a connected subgraph. So every yes-instance of $I_{ST(l)}$ will be mapped to a yes-instance of $I_{MWCS}$.
Consider a no-instance of $I_{ST(l)}$: There is no Steiner Tree $T=(V', E')$ with $|V'| \leq l$ that spans all $R$ vertices. This means that all Steiner trees contain $|V'| > k$ vertices. So in $G$, any subgraph $T$ with a weight $w(T) \geq r$ contains more than $k$ vertices. If there would be a subgraph with $k$ vertices or less, then in $G$ there should be a steiner tree of $l$ vertices or less. But there is not since we are considering a no-instance. So every no-instance of $I_{ST(l)}$ will be mapped to a no-instance of $I_{MWCS}$. End of proof
I think the proof is quite oke, except for the no-instance part. Anyone suggestions to improve this?