0
$\begingroup$

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

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

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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