18

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?

Thank you in advance.

TCS-user-23
  • 99
  • 6
Aaron Schild
  • 367
  • 1
  • 9
  • 6
    It should be emphased that $k$ is part of the input (not only $G$). Otherwise the problem is easy to solve. – user13136 May 05 '13 at 10:14
  • 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. – Yixin Cao May 06 '13 at 18:42

0 Answers0