<p>In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is maximized. The subgraph is not required to be connected.</p>

<p>There are conflicting sources on the complexity of this problem on planar graphs. Wikipedia claims that this problem is $\mathsf{NP}$-complete on planar graphs. <a href="https://cs.uwaterloo.ca/~brecht/papers/getpaper.php?file=jcmcc-1991.pdf" rel="nofollow">Keil and Brecht</a>  prove that the <em>connected</em> variant of the problem is $\mathsf{NP}$-complete on planar graphs, but leave the complexity of the densest $k$-subgraph problem as stated above open. <a href="http://www.ricoz.net/assets/slides_and_posters/FlowInterdiction-slides.pdf" rel="nofollow">Zenklusen</a> claims that the problem is still open. There are other sources that take both sides, but no source that I have seen gives a proof that planar densest $k$-subgraph is $\mathsf{NP}$-complete.</p>

<p><strong>What is the complexity of the densest k-subgraph problem on planar graphs?</strong></p>

<p>Thank you in advance.</p>

CC BY-SA 3.0
2013-05-05T10:14:12.757Z
It should be emphased that $k$ is part of the input (not only $G$). Otherwise the problem is easy to solve.
user13136
CC BY-SA 3.0
2013-05-06T18:42:58.857Z
I've spent some time on this problem a couple of months ago, and as far as I know, it still open for planar graphs (and proper interval graphs).  However, it seems impossible (for anybody) to give an answer like this, as one cannot be sure that there is no proof hidden in some corner.
Yixin Cao
<reference-request><np-hardness><planar-graphs>
Complexity of the densest $k$-subgraph problem on planar graphs
Aaron Schild
# Complexity of the densest $k$-subgraph problem on planar graphs

(Asked by: username_0 on 2013-05-03)

In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is maximized. The subgraph is not required to be connected.

There are conflicting sources on the complexity of this problem on planar graphs. Wikipedia claims that this problem is $\mathsf{NP}$-complete on planar graphs. [Keil and Brecht](https://cs.uwaterloo.ca/~brecht/papers/getpaper.php?file=jcmcc-1991.pdf) prove that the *connected* variant of the problem is $\mathsf{NP}$-complete on planar graphs, but leave the complexity of the densest $k$-subgraph problem as stated above open. [Zenklusen](http://www.ricoz.net/assets/slides_and_posters/FlowInterdiction-slides.pdf) claims that the problem is still open. There are other sources that take both sides, but no source that I have seen gives a proof that planar densest $k$-subgraph is $\mathsf{NP}$-complete.

**What is the complexity of the densest k-subgraph problem on planar graphs?**

Thank you in advance.

**Tags:** reference-request, np-hardness, planar-graphs

> **Comments:**
> **username_1**: It should be emphased that $k$ is part of the input (not only $G$). Otherwise the problem is easy to solve.  
> **username_2**: I've spent some time on this problem a couple of months ago, and as far as I know, it still open for planar graphs (and proper interval graphs).  However, it seems impossible (for anybody) to give an answer like this, as one cannot be sure that there is no proof hidden in some corner.  

---

## 0 answers

