1
$\begingroup$

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?

$\endgroup$
4
  • $\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$ Mar 22, 2018 at 15:10
  • $\begingroup$ @ManuelLafond Thanks a lot. This answer my question completely. $\endgroup$
    – Jiro
    Mar 22, 2018 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, 2018 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$
    – Jiro
    Mar 23, 2018 at 11:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.