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

<p>N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos
Exact and approximation algorithms for densest <span class="math-container">$k$</span>-subgraph
WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125</p>

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

CC BY-SA 4.0
2019-04-19T21:24:05.837Z
2019-04-19T21:24:05.837Z
Christian Komusiewicz
<p>The <em>densest k subgraph problem</em> aims to find a subgraph <span class="math-container">$H$</span> of a graph <span class="math-container">$G$</span> with exactly <span class="math-container">$k$</span> vertices that maximizes the number of edges <span class="math-container">$|E(H)|$</span>.</p>

<p>Does anyone know if there exists a polynomial-time algorithm for this problem under the restriction that <span class="math-container">$G$</span> is outerplanar? (Note: I am specifically asking for an algorithm, not a PTAS, and I want <span class="math-container">$G$</span> to be outerplanar, not <span class="math-container">$b$</span>-outerplanar for some <span class="math-container">$b &gt; 1$</span>).</p>

CC BY-SA 4.0
2019-04-19T10:40:58.307Z
Is $k$ a constant, or is it given as part of the input?
Emil Jeřábek
CC BY-SA 4.0
2019-04-19T10:42:09.227Z
Also, since $|V(H)|$ is fixed, you are simply maximizing $|E(H)|$, right?
Emil Jeřábek
CC BY-SA 4.0
2019-04-19T12:43:35.147Z
This can be done in polynomial time by dynamic programming.
Gamow
CC BY-SA 4.0
2019-04-20T15:00:49.617Z
In my view densest-k-subgraph is not particularly interesting for "hereditarily sparse" graphs.
Chandra Chekuri
CC BY-SA 4.0
2019-04-20T18:43:15.483Z
@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.
Christian Komusiewicz
CC BY-SA 4.0
2019-04-21T00:39:33.230Z
@EmilJeřábek $k$ is a constant, and yes you are correct, the goal is to maximize $|E(H)|$.
ChimiSeanGa
CC BY-SA 4.0
2019-04-21T07:30:57.190Z
Well, if $k$ is constant, you don’t need any sophisticated approach, you can do it in polynomial time $O(n^k)$ on arbitrary graphs by brute force enumeration.
Emil Jeřábek
<graph-theory><graph-algorithms><planar-graphs>
Densest k subgraph problem for outerplanar graphs?
ChimiSeanGa
# Densest k subgraph problem for outerplanar graphs?

(Asked by: username_0 on 2019-04-19)

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

**Tags:** graph-theory, graph-algorithms, planar-graphs
> **Comments:**
> **username_1**: Is $k$ a constant, or is it given as part of the input?  
> **username_1**: Also, since $|V(H)|$ is fixed, you are simply maximizing $|E(H)|$, right?  
> **username_2**: This can be done in polynomial time by dynamic programming.  
> **username_3**: In my view densest-k-subgraph is not particularly interesting for "hereditarily sparse" graphs.  
> **username_4**: @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.  
> **username_0**: @EmilJeřábek $k$ is a constant, and yes you are correct, the goal is to maximize $|E(H)|$.  
> **username_1**: Well, if $k$ is constant, you don’t need any sophisticated approach, you can do it in polynomial time $O(n^k)$ on arbitrary graphs by brute force enumeration.  

---

## 1 answers

### Answer by username_4 on 2019-04-19. Score: 5 | Accepted answer

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.


---

