# Densest k subgraph problem for outerplanar graphs?

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$$).

• Is $k$ a constant, or is it given as part of the input? – Emil Jeřábek supports Monica Apr 19 at 10:40
• Also, since $|V(H)|$ is fixed, you are simply maximizing $|E(H)|$, right? – Emil Jeřábek supports Monica Apr 19 at 10:42
• This can be done in polynomial time by dynamic programming. – Gamow Apr 19 at 12:43
• In my view densest-k-subgraph is not particularly interesting for "hereditarily sparse" graphs. – Chandra Chekuri Apr 20 at 15:00
• @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. – C Komus Apr 20 at 18:43

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.