# Complexity of the densest $k$-subgraph problem on planar graphs

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 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 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?

• It should be emphased that $k$ is part of the input (not only $G$). Otherwise the problem is easy to solve. – user13136 May 5 '13 at 10:14