Find the subgraph of $k$ nodes with the largest edge wights and node weights

Question

Let $W$ present the weighted adjacency matrix, $y$ is the indicator vector with $y_i=1$ meaning node $i$ is selected. $H$ is the vector with node weights. Then the problem become:

$\max:\ \ y^TWy+y^TH\\ s.t. \ \ \ \ \ \ y^T1 = k, y_i \in \{0,1\}.$

Is this problem NP hard? If not, any efficient algorithm?

Answer 1

It is NP-hard, which can be proved by reduction from the $k$-clique problem. The $k$-clique problem is as follows.

Given an undirected graph $G$ and an integer $k$, return a $k$-clique in $G$ if one exists and return null otherwise.

Let the weights of all edges in $G$ be $1$ and the weights of all nodes be $0$. Let $W$, $H$ be defined as stated in the question. Suppose $y^*$ be the optimum result of the optimization problem. Then if $${y^*}^TW{y^*} + {y^*}^TH = \frac{k(k-1)}{2}$$ all nodes whose corresponding entries in $y^*$ are $1$ constitute a $k$-clique in $G$; otherwise, there does not exist a $k$-clique in $G$.