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?

  • $\begingroup$ 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). $\endgroup$ – Manuel Lafond Mar 22 '18 at 15:10
  • $\begingroup$ @ManuelLafond Thanks a lot. This answer my question completely. $\endgroup$ – Sebastian Schlecht Mar 22 '18 at 15:51
  • $\begingroup$ 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. $\endgroup$ – Neal Young Mar 23 '18 at 1:03
  • $\begingroup$ @NealYoung Thanks, good to know. The densest k-subgraph seems to be NP-hard, too. I'll look into the approximation methods. $\endgroup$ – Sebastian Schlecht Mar 23 '18 at 11:59

Your Answer

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

Browse other questions tagged or ask your own question.