  A proportionally dense subgraph (PDS) of a graph is an induced subgraph of
size at least two such that every vertex in the subgraph has proportionally as
many neighbors inside as outside of the subgraph. Then, maxPDS is the problem
of determining a PDS of maximum size in a given graph. If we further require
that a PDS induces a connected subgraph, we refer to such problem as connected
maxPDS. In this paper, we study the complexity of maxPDS with respect to
parameters representing the density of a graph and its complement. We consider
$\Delta$, representing the maximum degree, $h$, representing the $h$-index, and
degen, representing the degeneracy of a graph. We show that maxPDS is NP-hard
parameterized by $\Delta,h$ and degen. More specifically, we show that maxPDS
is NP-hard on graphs with $\Delta=4$, $h=4$ and degen=2. Then, we show that
maxPDS is NP-hard when restricted to dense graphs, more specifically graphs $G$
such that $\Delta(\overline{G})\leq 6$, and graphs $G$ such that
$degen(\overline{G}) \leq 2$ and $\overline{G}$ is bipartite, where
$\overline{G}$ represents the complement of $G$. On the other hand, we show
that maxPDS is polynomial-time solvable on graphs with $h\le2$. Finally, we
consider graphs $G$ such that $h(\overline{G})\le 2$ and show that there exists
a polynomial-time algorithm for finding a PDS of maximum size in such graphs.
This result implies polynomial-time complexity on graphs with $n$ vertices of
minimum degree $n-3$, i.e. graphs $G$ such that $\Delta(\overline{G})\le 2$.
For each result presented in this paper, we consider connected maxPDS and
explain how to extend it when we require connectivity.
