# Finding a Minimal k-Subgraph

Given a complete, positively weighted, bidirectional graph with $n$ nodes without self-loops. Hence the corresponding adjacency matrix $A$ is positive, symmetric, and has zero main diagonal. I am searching for a subgraph with $k$ nodes such that the sum of weights is minimal.

In terms of the adjacency matrix, this is: $$\min_{K \subset \{1,2,\dots,n\}, |K| = k} \sum_{i,j \in K} A_{ij}$$

Is there a solution better than testing all $K$? Is there a related problem where I can start my search?

• In the case of $0$-$1$ weights, by taking the complement of your graph you end up with a densest $k$-subgraph instance (en.wikipedia.org/wiki/Dense_subgraph#Densest_k_subgraph). – Manuel Lafond Mar 22 '18 at 15:10
• @ManuelLafond Thanks a lot. This answer my question completely. – Sebastian Schlecht Mar 22 '18 at 15:51
• Note that Independent Set reduces easily to your problem as well, such that your problem has a solution of cost zero if and only if the given graph has an independent set of size k. So there is no poly-time multiplicative-factor approximation algorithm unless P=NP. – Neal Young Mar 23 '18 at 1:03
• @NealYoung Thanks, good to know. The densest k-subgraph seems to be NP-hard, too. I'll look into the approximation methods. – Sebastian Schlecht Mar 23 '18 at 11:59