The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$.

Does anyone know if there exists a polynomial-time algorithm for this problem under the restriction that $G$ is outerplanar? (Note: I am specifically asking for an algorithm, not a PTAS, and I want $G$ to be outerplanar, not $b$-outerplanar for some $b > 1$).

  • $\begingroup$ Is $k$ a constant, or is it given as part of the input? $\endgroup$ – Emil Jeřábek Apr 19 at 10:40
  • $\begingroup$ Also, since $|V(H)|$ is fixed, you are simply maximizing $|E(H)|$, right? $\endgroup$ – Emil Jeřábek Apr 19 at 10:42
  • 2
    $\begingroup$ This can be done in polynomial time by dynamic programming. $\endgroup$ – Gamow Apr 19 at 12:43
  • $\begingroup$ In my view densest-k-subgraph is not particularly interesting for "hereditarily sparse" graphs. $\endgroup$ – Chandra Chekuri Apr 20 at 15:00
  • $\begingroup$ @ChandraChekuri Can you explain a bit more what you mean by this? First, what exactly is a "hereditarily sparse" graph? Does this include e.g. graphs with low degeneracy? Because in these, Densest-k-Subgraph does have manyapplications, so it is at least interesting from an application point of view. $\endgroup$ – C Komus Apr 20 at 18:43

It can be solved in linear time in an even more general class of graphs: As shown in

N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos Exact and approximation algorithms for densest $k$-subgraph WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125

the Densest-$k$-Subgraph problem can be solved in $O(2^{\mathrm{tw}(G)}\cdot k \cdot ((\mathrm{tw}(G)^2)+k)\cdot |X|)$ time when a tree decomposition $(X,T)$ of the input graph $G$ is given. Since outerplanar graphs have treewidth at most two, the Densest-$k$-Subgraph can be solved in $O(k^2 n)$ time on outerplanar graphs with $n$ vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.