<p>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. </p>

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

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

CC BY-SA 3.0
2018-03-22T15:10:10.793Z
In the case of $0$-$1$ weights, by taking the complement of your graph you end up with a densest $k$-subgraph instance (https://en.wikipedia.org/wiki/Dense_subgraph#Densest_k_subgraph).
Manuel Lafond
CC BY-SA 3.0
2018-03-22T15:51:37.440Z
@ManuelLafond Thanks a lot. This answer my question completely.
Jiro
CC BY-SA 3.0
2018-03-23T01:03:37.563Z
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
CC BY-SA 3.0
2018-03-23T11:59:09.997Z
@NealYoung Thanks, good to know. The densest k-subgraph seems to be NP-hard, too. I'll look into the approximation methods.
Jiro
<graph-theory><matrices>
Finding a Minimal k-Subgraph
Jiro
# Finding a Minimal k-Subgraph

(Asked by: username_0 on 2018-03-22)

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?

**Tags:** graph-theory, matrices

> **Comments:**
> **username_1**: In the case of $0$-$1$ weights, by taking the complement of your graph you end up with a densest $k$-subgraph instance (https://en.wikipedia.org/wiki/Dense_subgraph#Densest_k_subgraph).  
> **username_0**: @ManuelLafond Thanks a lot. This answer my question completely.  
> **username_2**: 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.  
> **username_0**: @NealYoung Thanks, good to know. The densest k-subgraph seems to be NP-hard, too. I'll look into the approximation methods.  

---

## 0 answers

