$\mathrm{DkS}(H,k)$ of Densest $k$-Subgraph, and so
$\mathrm{OPT_{DkS}}(H,2k_{1}k_{2})\geq
k_{1}k_{2}\cdot\mathrm{OPT_{BDkS}}(G,k_{1},k_{2})$.

In order to complete the reduction, we need the following claim.

######  Claim A.2.

There is an efficient algorithm, that, given any solution $W$ to the instance
$\mathrm{DkS}(H,k)$ of the Densest $k$-Subgraph problem, computes a solution
to instance $\mathrm{BDkS}(G,k_{1},k_{2})$ of Bipartite Densest
$(k_{1},k_{2})$-Subgraph, whose value is at least $|E_{H}(W)|/(4k_{1}k_{2})$.

Proof: Denote $W_{A}=W\cap A$ and $W_{B}=W\cap B$. We start by computing a
partition $(W^{0}_{A},\ldots,W^{2k_{2}-1}_{A})$ of the vertices of $W_{A}$
into $2k_{2}$ subsets, containing at most $k_{1}$ vertices each, so that, for
every vertex $u$ of $A$, no two copies of $u$ appear in the same subset.

In order to do so, we let $\sigma$ be an arbitrary ordering of the vertices of
$W_{A}$, in which, for every vertex $u\in A$, all copies of $u$ that belong to
$W_{A}$ appear consecutively. For all $0\leq i\leq 2k_{2}-1$, we let
$W^{i}_{A}\subseteq W_{A}$ to be the set of all vertices $x\in W_{A}$, whose
index is $i\text{ }(\text{mod }2k_{2})$ in this ordering. Since, for every
vertex $u\in A$, $|T_{u}|=k_{2}$, it is immediate to verify that all copies of
$u$ in $W_{A}$ lie in distinct sets. It is also immediate to verify that, for
all $0\leq i<2k_{2}$, $|W^{i}_{A}|\leq k_{1}$.

We similarly compute a partition $(W^{0}_{B},\ldots,W^{2k_{1}-1}_{B})$ of the
vertices of $W_{B}$ into $2k_{1}$ subsets, containing at most $k_{2}$ vertices
each, so that, for every vertex $v$ of $B$, no two copies of $v$ appear in the
same subset.

Let $0\leq i^{*}<2k_{2},0\leq j^{*}<2k_{1}$ be a pair of indices, for which
$|E_{H}(W^{i^{*}}_{A},W^{j^{*}}_{B})|$ is maximized. Clearly,
$|E_{H}(W^{i^{*}}_{A},W^{j^{*}}_{B})|\geq|E_{H}(W)|/(4k_{1}k_{2})$. Finally,
let $X\subseteq V(G)$ be the set of vertices containing every vertex $u\in
V(G)$, whose copy lies in $W^{i^{*}}_{A}\cup W^{j^{*}}_{B}$. Note that $|X\cap
A|=|W^{i^{*}}_{A}|\leq k_{1}$ and $|X\cap B|=|W^{j^{*}}_{B}|\leq k_{2}$ must
hold, so $X$ is a valid solution to instance $\mathrm{BDkS}(G,k_{1},k_{2})$ of
Bipartite Densest $(k_{1},k_{2})$-Subgraph. Since $W^{i^{*}}_{A}\cup
W^{j^{*}}_{B}$ contains at most one copy of every vertex of $V(G)$, from the
construction of graph $H$, it is easy to verify that
$|E_{G}(X)|=|E_{H}(W^{i^{*}}_{A},W^{j^{*}}_{B})|\geq|E_{H}(W)|/(4k_{1}k_{2})$.

We are now ready to complete our reduction. We apply the approximation
algorithm ${\mathcal{A}}$ for the Densest $k$-Subgraph problem to instance
$\mathrm{DkS}(H,k)$, to obtain a solution $W$. Since $|V(H)|\leq N^{2}$, and
since ${\mathcal{A}}$ is a factor-$\alpha(n)$ approximation algorithm, from
A.1, we get that:

$|E_{H}(W)|\geq\frac{\mathrm{OPT_{DkS}}(H,k)}{\alpha(N^{2})}\geq\frac{k_{1}\cdot
k_{2}\cdot\mathrm{OPT_{BDkS}}(G,k_{1},k_{2})}{\alpha(N^{2})}.$

Additionally, the running time of the algorithm is $O(T(N^{2}))$.

We then apply the algorithm from A.2, whose running time is bounded by
$O(\textnormal{poly}(N))$ to solution $W$ to instance $\mathrm{DkS}(H,k)$, to
obtain a solution $X$ to instance $\mathrm{DkS}(G,k_{1},k_{2})$ of Bipartite
Densest $(k_{1},k_{2})$-Subgraph. We are guaranteed that:

$|E_{G}(X)|\geq\frac{|E_{H}(W)|}{4k_{1}k_{2}}\geq\Omega\bigg{(}\frac{\mathrm{OPT_{DkS}}(G,k_{1},k_{2})}{\alpha(N^{2})}\bigg{)}.$

It is easy to verify that the running time of the algorithm is bounded by
$O(T(N^{2})\cdot\textnormal{poly}(N))$.

###  A.2 Reduction from Densest $k$-Subgraph to Bipartite Densest
$(k_{1},k_{2})$-Subgraph

We now assume that there exists an efficient $\alpha(N)$-approximation
algorithm ${\mathcal{A}}^{\prime}$ for the Bipartite Densest
$(k_{1},k_{2})$-Subgraph problem, where $N$ is the number of vertices in the
input graph. We show that there exists an efficient
$O(\alpha(2n))$-approximation algorithm for the Densest $k$-Subgraph problem,
where $n$ is the number of vertices in the input graph.

Let $\mathrm{DkS}(G,k)$ be the input instance for the Densest $k$-Subgraph
problem, so $|V(G)|=n$. We construct a bipartite graph $H=(V_{1},V_{2},E)$,
where the vertex sets are $V_{1}=\\{u^{1}\mid u\in V(G)\\}$,
$V_{2}=\\{u^{2}\mid u\in V(G)\\}$, and the edge set is
$E=\\{(u^{1},v^{2}),(u^{2},v^{1})\mid(u,v)\in E(G)\\}$. We denote
$N=|V(H)|=2n$. Consider the instance $\mathrm{DkS}(H,k_{1},k_{2})$ of
Bipartite Densest $(k_{1},k_{2})$-Subgraph, where $k_{1}=k_{2}=k$. We use the
following observation to lower-bound the optimal solution cost of this
instance.

######  Observation A.3.

$\mathrm{OPT_{BDkS}}(H,k_{1},k_{2})\geq 2\cdot\mathrm{OPT_{DkS}}(G,k)$.

Proof: Let $V^{*}$ be the optimal solution to instance $\mathrm{DkS}(G,k)$ of
Densest $k$-Subgraph. We define $U^{*}=\\{v^{1},v^{2}\mid v\in V^{*}\\}$, so
$|U^{*}\cap V_{1}|=k$ and $|U^{*}\cap V_{2}|=k$. Clearly, $U^{*}$ is a
feasible solution to instance $\mathrm{BDkS}(H,k,k)$. Moreover, it is easy to
verify that $|E_{H}(U^{*})|=2\cdot|E_{G}(V^{*})|$, so
$\mathrm{OPT_{BDkS}}(H,k_{1},k_{2})\geq 2\cdot\mathrm{OPT_{DkS}}(G,k)$.

We apply Algorithm ${\mathcal{A}}^{\prime}$ to instance,
$\mathrm{DkS}(H,k_{1},k_{2})$ of Bipartite Densest $(k_{1},k_{2})$-Subgraph,
obtaining a solution $U^{\prime}$. We denote $U_{1}=U^{\prime}\cap V_{1}$ and
$U_{2}=U^{\prime}\cap V_{2}$, so $|U_{1}|=|U_{2}|=k$, and
$|E_{H}(U_{1},U_{2})|\geq\mathrm{OPT_{BDkS}}(H,k,k)/\alpha(N)\geq
2\mathrm{OPT_{DkS}}(G,k)/\alpha(2n)$ from A.3.

Let $U=\\{v\mid v^{1}\in U_{1}\text{ or }v^{2}\in U_{2}\\}$ be a subset of
vertices of $G$. Clearly, $|U|\leq 2k$, and
$|E_{G}(U)|\geq\frac{|E_{H}(U^{*})|}{2}\geq\frac{\mathrm{OPT_{DkS}}(G,k)}{\alpha(2n)}$.

We then apply the algorithm from Lemma 2.3 to graph $G$ and set $U$ of
vertices, with parameter $\beta=1/2$, to obtain a set $\tilde{U}\subseteq U$
of vertices, with $|\tilde{U}|\leq k$, and
$|E_{G}(\tilde{U})|\geq\Omega(|E_{G}(U)|)\geq\Omega(\mathrm{OPT_{DkS}}(G,k)/\alpha(2n))$.
Therefore, we obtained an $O(\alpha(2n))$-approximate solution to instance
$\mathrm{DkS}(G,k)$ of the Densest $k$-Subgraph problem.

##  Appendix B Reduction from (r,h)-Graph Partitioning to Densest $k$-Subgraph

In this section we complete the proof Theorem 4.1, by showing a reduction from
(r,h)-Graph Partitioning to Densest $k$-Subgraph. The reduction is very
similar to the reduction from Dense $k$-Coloring to Densest $k$-Subgraph
described in Section 4.

We start by formulating an LP-relaxation of the problem, whose number of
constraints is bounded by $O(N)$, but the number of variables may be large. We
then show an LP-rounding algorithm for this LP-relaxation, whose running time
is $O(\textnormal{poly}(N))$ if it is given a solution to the LP-relaxation
whose support size is bounded by $O(\textnormal{poly}(N))$. In order to
compute an approximate LP-solution whose support size is sufficiently small,
we design an approximate separation oracle for the dual of the LP-relaxation.
We start with describing the LP-relaxation and providing an LP-rounding
algorithm for it.

###  B.1 Linear Programming Relaxation and an LP-Rounding Algortihm

Let $\mathrm{GP}(G,r,h)$ be the input instance of (r,h)-Graph Partitioning,
and denote $|V(G)|=N$. We let ${\mathcal{H}}$ be the collection of all
subgraphs $H\subseteq G$ with $|E(H)|\leq h$. For each such subgraph $H$, we
denote $m(H)=|E(H)|$. We consider the following LP-relaxation of the
(r,h)-Graph Partitioning problem, that has a variable $x_{H}$ for every graph
$H\in{\mathcal{H}}$.

(LPW-P) $\displaystyle\max$ $\displaystyle\sum_{H\in{\mathcal{H}}}m(H)\cdot
x_{H}$ s.t. $\displaystyle\sum_{\stackrel{{\scriptstyle
H\in{\mathcal{H}}:}}{{v\in V(H)}}}x_{H}\leq 1$ $\displaystyle\forall v\in
V(G)$ $\displaystyle\sum_{H\in{\mathcal{H}}}x_{H}\leq r$ $\displaystyle
x_{H}\geq 0$ $\displaystyle\forall H\in{\mathcal{H}}$

It is easy to verify that (LPW-P) is an LP-relaxation of the (r,h)-Graph
Partitioning problem. Indeed, consider a solution $(H_{1},\ldots,H_{r})$ to
the input instance $\mathrm{GP}(G,r,h)$. For all $1\leq i\leq r$, we set
$x_{H_{i}}=1$, and for every other graph $H\in{\mathcal{H}}$, we set
$x_{H}=0$. This provides a feasible solution to (LPW-P), whose value is
precisely $\sum_{i=1}^{r}|E(H)|$. We denote the value of the optimal solution
to (LPW-P) by $\text{OPT}_{\textnormal{LP-P}}$. From the above discussion,
$\text{OPT}_{\textnormal{LP-P}}\geq\mathrm{OPT_{GP}}(G,r,h)$.

In the following claim we provide an LP-rounding algorithm for (LPW-P). The
claim is an analogue of 4.2. Its proof is almost identical and is provided
here for completeness.

######  Claim B.1.

There is an efficient randomized algorithm, whose input consists of an
instance $\mathrm{GP}(G,r,h)$ of the (r,h)-Graph Partitioning problem with
$N=|V(G)|$, such that $N$ is greater than a large enough constant, and a
solution $\\{x_{H}\mid H\in{\mathcal{H}}\\}$ to (LPW-P), in which the number
of variables $x_{H}$ with $x_{H}>0$ is bounded by $O(\textnormal{poly}(N))$,
and $\sum_{H\in{\mathcal{H}}}m(H)\cdot
x_{H}\geq\text{OPT}_{\textnormal{LP-P}}/\beta$, for some parameter
$1\leq\beta\leq N^{3}$; the solution is given by only specifying values of
variables $x_{H}$ that are non-zero. The algorithm with high probability
returns an integral solution $(H_{1},\ldots,H_{r})$ to instance
$\mathrm{GP}(G,r,h)$, such that
$\sum_{i=1}^{r}|E(H_{i})|\geq\frac{\mathrm{OPT_{GP}}(G,r,h)}{2000\beta\log^{3}N}$.

Proof: We assume that we are given a solution $\\{x_{H}\mid
H\in{\mathcal{H}}\\}$ to (LPW-P), in which the number of variables $x_{H}$
with $x_{H}>0$ is bounded by $O(\textnormal{poly}(N))$. Denote
$C=\sum_{H\in{\mathcal{H}}}m(H)\cdot x_{H}$, and recall that
$C\geq\text{OPT}_{\textnormal{LP-P}}/\beta$ holds. We denote by
${\mathcal{H}}^{\prime}\subseteq{\mathcal{H}}$ the collection of all graphs
$H\in{\mathcal{H}}$ with $x_{H}>0$.

We construct another collection
${\mathcal{H}}^{\prime\prime}\subseteq{\mathcal{H}}^{\prime}$ of subgraphs of
$G$ as follows. For every subgraph $H\in{\mathcal{H}}^{\prime}$, we add $H$ to
${\mathcal{H}}^{\prime\prime}$ independently, with probability $x_{H}$.
Clearly, $\text{\bf
E}\left[\sum_{H\in{\mathcal{H}}^{\prime\prime}}m(H)\right]=\sum_{H\in{\mathcal{H}}}m(H)\cdot
x_{H}=C$.

We say that a bad event ${\cal{E}}_{1}$ happens if some vertex $v\in V(G)$
lies in more than $5\log N$ graphs in ${\mathcal{H}}^{\prime\prime}$. We say
that a bad event ${\cal{E}}_{2}$ happens if
$|{\mathcal{H}}^{\prime\prime}|>5r\log N$. We say that a bad event
${\cal{E}}_{3}$ happens if
$\sum_{H\in{\mathcal{H}}^{\prime\prime}}m(H)<\frac{C}{8}$. Lastly, we say that
a bad event ${\cal{E}}$ happens if either of the events
${\cal{E}}_{1},{\cal{E}}_{2}$, or ${\cal{E}}_{3}$ happen. The following
observation is an analogue of 4.3. Its proof is identical and is omitted here.

######  Observation B.2.

$\text{\bf Pr}\left[{\cal{E}}\right]\leq 2/N^{3}$.

Observe that we can efficiently check whether Event ${\cal{E}}$ happened. If
Event ${\cal{E}}$ happens, then we terminate the algorithm with a FAIL. We
assume from now on that Event ${\cal{E}}$ did not happen. Then
$\sum_{H\in{\mathcal{H}}^{\prime\prime}}m(H)\geq\frac{C}{8}\geq\frac{\mathrm{OPT_{GP}}(G,r,h)}{8\beta}$
must hold. We denote
${\mathcal{H}}^{\prime\prime}=\\{H_{1},H_{2},\ldots,H_{z}\\}$, where the
graphs are indexed according to their value $m(H)$, so that $m(H_{1})\geq
m(H_{2})\geq\cdots\geq m(H_{z})$. We then let
${\mathcal{H}}^{*}=\\{H_{1},\ldots,H_{r}\\}$ (if $z<r$, then we set
$H_{z+1}=\cdots=H_{r}=\emptyset$). For all $1\leq i\leq r$, we denote
$E_{i}=E(H_{i})$, so $|E_{i}|=m(H_{i})$. Recall that, since Event ${\cal{E}}$
did not happen, $|{\mathcal{H}}^{\prime\prime}|\leq 5r\log N$ holds.
Therefore:

$\sum_{i=1}^{r}|E_{i}|\geq\frac{\sum_{H\in{\mathcal{H}}^{\prime\prime}}m(H)}{5\log
N}\geq\frac{\mathrm{OPT_{GP}}(G,r,h)}{40\beta\log N}.$

As before, the graphs in set ${\mathcal{H}}$ may not be mutually disjoint.
However, since Event ${\cal{E}}$ did not happen, every vertex of $V(G)$ may
lie in at most $5\log N$ such graphs. We now construct a new collection
${\mathcal{H}}^{**}=\\{H_{1}^{\prime},\ldots,H_{r}^{\prime}\\}$ of graphs, as
follows. For all $1\leq i\leq r$, we will define a subset $V_{i}\subseteq
V(H_{i})$ of vertices, and we will then set $H_{i}^{\prime}=H_{i}[V_{i}]$. In
order to define vertex sets $V_{1},\ldots,V_{r}$, we start by setting
$V_{1}=V_{2}=\cdots=V_{r}=\emptyset$, and then process vertices $v\in V(H)$
one by one. Consider any vertex $v\in V(G)$, and let
$H_{i_{1}},H_{i_{2}},\ldots,H_{i_{a}}\in{\mathcal{H}}^{*}$ be the graphs of
${\mathcal{H}}^{*}$ containing $v$. Vertex $v$ chooses an index
$i^{*}\in\\{i_{1},\ldots,i_{a}\\}$ at random, and is then added to
$V_{i^{*}}$. Once all vertices of $V(G)$ are processed, we obtain a final
collection $V_{1},\ldots,V_{r}$ of sets of vertices, where for all $1\leq
i\leq r$, $V_{i}\subseteq V[H_{i}]$. For all $1\leq i\leq r$, we then set
$H^{\prime}_{i}=H_{i}[V_{i}]$. Since $H^{\prime}_{i}\subseteq H_{i}$, we are
then guaranteed that $|E(H^{\prime}_{i})|\leq h$ holds.

Note that for all $1\leq j\leq r$, for every vertex $v\in V(H_{j})$, the
probability that $v\in V_{j}$ is at least $1/(5\log N)$. We say that an edge
$e=(u,v)\in E_{j}$ _survives_ if both $u,v\in V_{j}$. We denote by
$E^{\prime\prime}\subseteq\bigcup_{i=1}^{r}E_{i}$ the set of all edges that
survive. Since $\text{\bf Pr}\left[u\in V_{j}\right]\geq 1/(5\log N)$,
$\text{\bf Pr}\left[v\in V_{j}\right]\geq 1/(5\log N)$, and the two events are
independent, we get that the probability that edge $e$ survives is at least
$1/(25\log^{2}N)$. Overall, we get that:

$\text{\bf
E}\left[|E^{\prime\prime}|\right]\geq\frac{\sum_{i=1}^{r}|E_{i}|}{25\log^{2}N}\geq\frac{\mathrm{OPT_{GP}}(G,r,h)}{1000\beta\log^{3}N}.$

The final solution to instance $\mathrm{GP}(G,r,h)$ is
${\mathcal{H}}^{**}=\\{H_{1}^{\prime},\ldots,H_{r}^{\prime}\\}$. Clearly, the
value of this solution is $|E^{\prime\prime}|$.

So far we have obtained a randomized algorithm that either returns FAIL (with
probability at most $2/N^{3}$), or it returns a solution to instance instance
$\mathrm{GP}(G,r,h)$ of the (r,h)-Graph Partitioning problem, whose expected
value is at least $\frac{\mathrm{OPT_{GP}}(G,r,h)}{1000\beta\log^{3}N}$.

Let $p^{\prime}$ be the probability that the algorithm returned a solution of
value at least $\frac{\mathrm{OPT_{GP}}(G,r,h)}{2000\beta\log^{3}N}$, given
that it did not return FAIL. Note that the expected solution value, assuming
the algorithm did not return FAIL, is at most
$\frac{\mathrm{OPT_{GP}}(G,r,h)}{2000\beta\log^{3}N}+p^{\prime}\cdot\mathrm{OPT_{GP}}(G,r,h)$.
Since this expectation is also at least
$\frac{\mathrm{OPT_{GP}}(G,r,h)}{1000\beta\log^{3}N}$, we get that
$p^{\prime}\geq\frac{1}{1000\beta\log^{3}N}$. Overall, the probability that
our algorithm successfully returns a solution of value at least
$\frac{\mathrm{OPT_{GP}}(G,r,h)}{2000\beta\log^{3}N}$ is
$p^{\prime}\cdot\text{\bf
Pr}\left[\neg{\cal{E}}\right]\geq\Omega\left(\frac{1}{\beta\log^{3}N}\right)$.
By repeating the algorithm $\textnormal{poly}(N)$ times we can ensure that it
successfully computes a solution of value at least
$\frac{\mathrm{OPT_{GP}}(G,r,h)}{2000\beta\log^{3}N}$ with high probability.

###  B.2 Approximately Solving the LP-Relaxation

In this subsection we provide an approximate separation oracle for the dual
linear program of (LPW-P). This is sufficient in order to obtain an algorithm
with running time $O(\textnormal{poly}(N))$ that approximately solves (LPW-P)
using the methods described in Section 4.2. The following Linear Program is a
Dual of (LPW-P). It has a variable $y_{v}$ for every vertex $v\in V(G)$, and
an additional variable $z$.

(LPW-D) $\displaystyle\min$ $\displaystyle r\cdot z+\sum_{v\in V(G)}y_{v}$
s.t. $\displaystyle z+\sum_{v\in V(H)}y_{v}\geq m(H)$ $\displaystyle\forall
H\in{\mathcal{H}}$ $\displaystyle z\geq 0$ $\displaystyle y_{v}\geq 0$
$\displaystyle\forall v\in V(G)$

We denote the value of the optimal solution to (LPW-D) by
$\text{OPT}_{\textnormal{LPW-D}}$.

The following lemma provides a randomized separation oracle for (LPW-D). It is
an analogue of Lemma 4.4, and its proof is essentially identical. We provide
it here for completeness.

######  Lemma B.3.

Assume that there is an efficient $\alpha(n)$-approximation algorithm for the
Densest $k$-Subgraph problem, where $\alpha$ is an increasing function, and
$n$ is the number of vertices in the input graph. Then there is a randomized
$\beta(N)$-approximate separation oracle for (LPW-D), where $N$ is the number
of variables in the input graph $G$, and
$\beta(N)=O(\alpha(N^{2})\cdot\log^{2}N)$.

Proof: Recall that we are given as input real values $z$ and $\\{y_{v}\mid
v\in V(G)\\}$. As before, we can efficiently check whether $z\geq 0$, and
whether $y_{v}\geq 0$ for all $v\in V(G)$. If this is not the case, we can
return the corresponding violated constraint.

We say that a subgraph $H\in{\mathcal{H}}$ is _bad_ if $z+\sum_{v\in
V(H)}y_{v}<m(H)/\beta$ holds, where $\beta=c\cdot\alpha(N^{2})\cdot\log^{2}N$,
and $c$ is a large enough constant whose value we set later. Our goal is to
design an efficient algorithm that either returns a violated constraint of the
LP (that is, a graph $H\in{\mathcal{H}}$ for which $z+\sum_{v\in
V(H)}y_{v}<m(H)$ holds); or it returns “accept”. We require that, if there
exists a bad subgraph $H\in{\mathcal{H}}$, then the probability that the
algorithm returns “accept” is at most $2/3$.

We slightly modify the input values in $\\{y_{v}\mid v\in V(G)\\}$, almost
exactly like in the proof of Lemma B.3. First, for every vertex $v\in V(G)$
with $y_{v}>h$, we let $y^{\prime}_{v}$ be the smallest integral power of $2$
that is greater than $h$, and for every vertex $v\in V(G)$ with $y_{v}<1/4$,
we set $y^{\prime}_{v}=0$. For each remaining vertex $v$, we let
$y^{\prime}_{v}$ be the smallest integral power of $2$ that is greater than
$4y_{v}$. Notice that, for every vertex $v$ with $y^{\prime}_{v}\neq 0$,
$1\leq y^{\prime}_{v}\leq 4h$ holds, and $y^{\prime}_{v}$ is an integral power
of $2$. We also set $z^{\prime}=2z$. We say that a subgraph
$H\in{\mathcal{H}}$ is _problematic_ if $z^{\prime}+\sum_{v\in
V(H)}y^{\prime}_{v}<8m(H)/\beta$ holds. We use the following two observations,
that are analogues of 4.5 and 4.6; their proofs are also almost identical.

######  Observation B.4.

If $H\in{\mathcal{H}}$ is a bad subgraph of $G$, then it is a problematic
subgraph of $G$.

Proof: Recall that, if $H$ is a bad subgraph, then $z+\sum_{v\in
V(H)}y_{v}<m(H)/\beta$ must hold. Since, for every vertex $v\in V(G)$,
$y^{\prime}_{v}\leq 8y_{v}$, and $z^{\prime}=2z$, we get that:

$z^{\prime}+\sum_{v\in V(H)}y^{\prime}_{v}\leq 2z+8\sum_{v\in V(H)}y_{v}\leq
8\left(z+\sum_{v\in V(H)}y_{v}\right)<8m(H)/\beta.$

Therefore, subgraph $H$ is problematic.

######  Observation B.5.

Assume that there exists a subgraph $H\in{\mathcal{H}}$, for which
$z^{\prime}+\sum_{v\in V(H)}y^{\prime}_{v}<m(H)$ holds. Let
$H^{\prime}\subseteq H$ be the graph obtained from $H$ after removing all
isolated vertices from it. Then $z+\sum_{v\in
V(H^{\prime})}y_{v}<m(H^{\prime})$ holds.

Proof: Since every vertex $v\in V(H)\setminus V(H^{\prime})$ is isolated in
$H$, we get that $m(H^{\prime})=|E(H^{\prime})|=|E(H)|=m(H)$. We partition the
vertices of $H^{\prime}$ into two subsets: set $X$ containing all vertices
$v\in V(H^{\prime})$ with $y_{v}<1/4$, and set $Y$ containing all remaining
vertices. Clearly, $\sum_{v\in
X}y_{v}<\frac{|X|}{4}\leq\frac{m(H^{\prime})}{2}$ (since
$m(H^{\prime})\geq|V(H^{\prime})|/2\geq|X|/2$, as graph $H^{\prime}$ contains
no isolated vertices).

Assume for contradiction that $z+\sum_{v\in V(H^{\prime})}y_{v}\geq
m(H^{\prime})$. Then:

$z+\sum_{v\in Y}y_{v}\geq m(H^{\prime})-\sum_{v\in X}y_{v}\geq
m(H^{\prime})/2.$

We now consider two cases. The first case is when there is some vertex $v\in
Y$ with $y_{v}\geq h$. In this case, $y^{\prime}_{v}\geq h$ holds, and
$z^{\prime}+\sum_{v\in S}y^{\prime}_{v}\geq h>m(H^{\prime})$ holds, a
contradiction.

Otherwise, for every vertex $v\in Y$, $y^{\prime}_{v}\geq 4y_{v}$ holds. Since
$z^{\prime}=2z$ also holds, we get that:

$z^{\prime}+\sum_{v\in V(H)}y^{\prime}_{v}\geq z^{\prime}+\sum_{v\in
Y}y^{\prime}_{v}\geq 2z+4\sum_{v\in Y}y_{v}\geq m(H^{\prime})=m(H),$

a contradiction.

From now on we focus on values $z^{\prime},\\{y^{\prime}_{v}\mid v\in
V(G)\\}$. It is now enough to design an efficient randomized algorithm, that
either computes a subgraph $H\in{\mathcal{H}}$, for which
$z^{\prime}+\sum_{v\in V(H)}y^{\prime}_{v}<m(H)$ holds, or returns “accept”.
It is enough to ensure that, if there is a problematic subraph
$H\in{\mathcal{H}}$, then the algorithm returns “accept” with probability at
most $2/3$. Indeed, if there is a bad subgraph $H\in{\mathcal{H}}$, then, from
B.4, there is a problematic subgraph, and the algorithm will return “accept”
with probability at most $2/3$. On the other hand, if the algorithm computes a
subgraph $H\in{\mathcal{H}}$ of vertices, for which $z^{\prime}+\sum_{v\in
S}y^{\prime}_{v}<m(S)$ holds, then we can return the subgraph
$H^{\prime}\subseteq H$ from the statement of B.5, that defines a violated
constraint with respect to the original LP-values.

Our algorithm is essentially the same as before: it computes a random
partition $(A,B)$ of the vertices of $G$, where every vertex $v\in V(G)$ is
independently added to $A$ or to $B$ with probability $1/2$ each. Let
$q=\left\lceil\log(8h)\right\rceil$. For all $1\leq i\leq q$, we define a set
$A_{i}\subseteq A$ of vertices: $A_{i}=\\{v\in A\mid
y^{\prime}_{v}=2^{i-1}\\}$, and we let $A_{0}=\\{v\in A\mid
y^{\prime}_{v}=0\\}$. Clearly, $(A_{0},\ldots,A_{q})$ is a partition of the
set $A$ of vertices.

We compute a partition $(B_{0},\ldots,B_{q})$ of the vertices of $B$
similarly. For all $0\leq i,j\leq q$, we denote by $E_{i,j}$ the set of all
edges $e=(u,v)$ with $u\in A_{i}$ and $v\in B_{j}$, and we define a bipartite
graph $G_{i,j}$, whose vertex set is $A_{i}\cup B_{j}$, and edge set is
$E_{i,j}$.

Recall that we have assumed that there is an efficient
$\alpha(n)$-approximation algorithm for the Densest $k$-Subgraph problem,
where $n$ is the number of vertices in the input graph. From Lemma 2.1, there
exists an efficient $O(\alpha(\hat{n}^{2}))$-approximation algorithm for the
Bipartite Densest $(k_{1},k_{2})$-Subgraph problem, where $\hat{n}$ is the
number of vertices in the input graph. We denote this algorithm by
${\mathcal{A}}^{\prime}$.

For every pair $0\leq i,j\leq q$ of integers, and every pair $0\leq
k_{1},k_{2}\leq N$ of integers, we apply Algorithm ${\mathcal{A}}^{\prime}$
for the Bipartite Densest $(k_{1},k_{2})$-Subgraph problem to graph $G_{i,j}$,
with parameters $k_{1}$ and $k_{2}$. Let $S_{i,j}^{k_{1},k_{2}}$ be the output
of this algorithm, and let $m_{i,j}^{k_{1},k_{2}}$ be the number of edges in
the subgraph of $G_{i,j}$ that is induced by the set $S_{i,j}^{k_{1},k_{2}}$
of vertices. We say that the application of algorithm ${\mathcal{A}}^{\prime}$
is _successful_ if $z^{\prime}+\sum_{v\in
S_{i,j}^{k_{1},k_{2}}}y^{\prime}_{v}<\min\\{h,m_{i,j}^{k_{1},k_{2}}\\}$, and
otherwise it is _unsuccessful_. If, for any quadruple $(i,j,k_{1},k_{2})$ of
indices, the application of algorithm ${\mathcal{A}}^{\prime}$ was successful,
then we return a graph $H$, that is defined as the subgraph of $G$ induced by
the set $S=S_{i,j}^{k_{1},k_{2}}$ of vertices; if this graph contains more
than $h$ edges, then we delete arbitrary edges from it, until $|E(H)|=h$
holds. Clearly, $H\in{\mathcal{H}}$ must hold. Moreover, we are guaranteed
that $z^{\prime}+\sum_{v\in
V(H)}y^{\prime}_{v}<\min\\{h,m_{i,j}^{k_{1},k_{2}}\\}\leq m(H)$, as required.
If every application of algorithm ${\mathcal{A}}^{\prime}$ is unsuccessful,
then we return “accept”. The following observation will finish the proof of
Lemma B.3. The observation is an analogue of 4.7 and its proof is essentially
identical.

######  Observation B.6.

Suppose there is a problematic subgraph $H\in{\mathcal{H}}$. Then the
probability that the algorithm returns “accept” is at most $2/3$.

Proof: Let $H\in{\mathcal{H}}$ be a problematic subgraph, and denote $S=V(H)$,
so $z^{\prime}+\sum_{v\in S}y^{\prime}_{v}<8m(S)/\beta$ holds. Let
$E^{\prime}=E(H)$, so $|E^{\prime}|=m(H)\leq h$.

Denote $A_{S}=A\cap S,B_{S}=B\cap S$, and let $E^{\prime\prime}\subseteq
E^{\prime}$ be the set of edges $e$, such that exactly one endpoint of $e$
lies in $A$. Clearly, for every edge $e\in E^{\prime}$, $\text{\bf
Pr}\left[e\in E^{\prime\prime}\right]=1/2$. Therefore, $\text{\bf
E}\left[|E^{\prime\prime}|\right]=|E^{\prime}|/2$. Let ${\cal{E}}^{\prime}$ be
the bad event that $|E^{\prime\prime}|<|E^{\prime}|/8$. Using the same
arguments as in the proof of 4.7, $\text{\bf
Pr}\left[{\cal{E}}^{\prime}\right]\leq 2/3$. Next, we show that, if Event
${\cal{E}}^{\prime}$ does not happen, then the algorithm does not return
“accept”.

From now on we assume that Event ${\cal{E}}^{\prime}$ did not happen, so
$|E^{\prime\prime}|\geq|E^{\prime}|/8$. Therefore:

$z^{\prime}+\sum_{v\in
S}y^{\prime}_{v}<\frac{8m(H)}{\beta}\leq\frac{64|E^{\prime\prime}|}{\beta}$

holds.

Clearly, there must be a pair $0\leq i,j\leq q$ of indices, such that
$|E^{\prime\prime}\cap
E_{i,j}|\geq\frac{|E^{\prime\prime}|}{4q^{2}}\geq\frac{|E^{\prime\prime}|}{128\log^{2}m}$.
We now fix this pair $i,j$ of indices, and denote $A^{\prime}_{i}=A_{i}\cap S$
and $B^{\prime}_{j}=B_{j}\cap S$. We also denote $k_{1}=|A^{\prime}_{i}|$ and
let $k_{2}=|B^{\prime}_{j}|$. Denote $M_{i,j}=|E^{\prime\prime}\cap E_{i,j}|$.
Fom our choice of indices $i,j$, we get that:

$z^{\prime}+\sum_{v\in A^{\prime}_{i}\cup B^{\prime}_{j}}y^{\prime}_{v}\leq
z^{\prime}+\sum_{v\in
S}y^{\prime}_{v}\leq\frac{64|E^{\prime\prime}|}{\beta}\leq\frac{M_{i,j}}{\beta}\cdot(2^{13}\cdot\log^{2}m).$

Notice that the set $S^{\prime}=A^{\prime}_{i}\cup B^{\prime}_{j}$ of vertices
provides a solution to the instance of the Bipartite Densest
$(k_{1},k_{2})$-Subgraph problem on graph $G_{i,j}$ with parameters
$k_{1},k_{2}$, whose value is at least $M_{i,j}$. Let
$S^{\prime\prime}=S_{i,j}^{k_{1},k_{2}}$ be the set of vertices obtained by
applying Algorithm ${\mathcal{A}}^{\prime}$ to graph $G_{i,j}$ with parameters
$k_{1},k_{2}$. Since $|V(G_{i,j})|\leq N$, and since ${\mathcal{A}}^{\prime}$
is an $O(\alpha(N^{2}))$-approximation algorithm for Bipartite Densest
$(k_{1},k_{2})$-Subgraph, we are guaranteed that
$|E_{G}(S^{\prime\prime})|\geq\Omega\left(\frac{M_{i,j}}{\alpha(N^{2})}\right)$.
Recall that $|A\cap S^{\prime\prime}|\leq k_{1}$; $A\cap
S^{\prime\prime}\subseteq A_{i}$, and all vertices $v\in A_{i}$ have an
identical value $y^{\prime}_{v}$. Therefore, $\sum_{v\in A\cap
S^{\prime\prime}}y^{\prime}_{v}\leq\sum_{v\in A^{\prime}_{i}}y^{\prime}_{v}$.
Using a similar reasoning, $\sum_{v\in B\cap
S^{\prime\prime}}y^{\prime}_{v}\leq\sum_{v\in B^{\prime}_{j}}y^{\prime}_{v}$.
Overall, we then get that:

$\begin{split}z^{\prime}+\sum_{v\in S^{\prime\prime}}y^{\prime}_{v}&\leq
z^{\prime}+\sum_{v\in S^{\prime}}y^{\prime}_{v}\\\
&\leq\frac{M_{i,j}}{\beta}\cdot(2^{13}\cdot\log^{2}m)\\\ &\leq
O\left(\frac{\alpha(N^{2})\cdot
2^{13}\cdot\log^{2}m}{\beta}\right)\cdot\min\\{|E_{G}(S^{\prime\prime})|,h\\}.\end{split}$

Recall that $\beta=c\cdot\alpha(N^{2})\cdot\log^{2}N$. By letting the value of
the constant $c$ be large enough, we can ensure that $z^{\prime}+\sum_{v\in
S^{\prime\prime}}y^{\prime}_{v}<\min\\{|E_{G}(S^{\prime\prime})|,h\\}$, and so
the application of algorithm ${\mathcal{A}}^{\prime}$ to graph $G_{i,j}$ with
parameters $k_{1}$ and $k_{2}$ is guaranteed to be successful. Therefore, if
Event ${\cal{E}}^{\prime}$ does not happen, and we set $c$ to be a large
enough constant, then our algorithm does not return ”accept”. Since $\text{\bf
Pr}\left[{\cal{E}}^{\prime}\right]\leq 2/3$, the observation follows.

We can use the separation oracle described in Lemma B.3 in order to obtain a
$\beta(N)$-approximate solution to (LPW-P), whose support size is bounded by
$O(\textnormal{poly}(N))$ using the standard techniques that were described in
Section 4.2; we do not repeat them here. By applying the LP-rounding algorithm
from B.1 to the resulting LP-solution, with high probability we obtain, in
time $O(\textnormal{poly}(N))$, an integral solution $(H_{1},\ldots,H_{r})$ to
instance $\mathrm{GP}(G,r,h)$, such that
$\sum_{i=1}^{r}|E(H_{i})|\geq\Omega\left(\frac{\mathrm{OPT_{GP}}(G,r,h)}{300\beta(N)\log^{3}N}\right)$.
Since $\beta(N)=O(\alpha(N^{2})\cdot\log^{2}N)$, with high probability we
obtain an $O(\alpha(N^{2})\cdot\textnormal{poly}\log N)$-approximate solution
to the input instance of (r,h)-Graph Partitioning.

## References

  * [AAM+11] Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein.  Inapproximabilty of densest k-subgraph from average case hardness.  Manuscript, 2011.  https://www.tau.ac.il/~nogaa/PDFS/dks8.pdf.
  * [ABS15] Sanjeev Arora, Boaz Barak, and David Steurer.  Subexponential algorithms for unique games and related problems.  Journal of the ACM (JACM), 62(5):1–25, 2015.
  * [ACNS82] M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi.  Crossing-free subgraphs.  Theory and Practice of Combinatorics, pages 9–12, 1982.
  * [ADD+93] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.
  * [AMS07] Christoph Ambuhl, Monaldo Mastrolilli, and Ola Svensson.  Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 329–337. IEEE, 2007.
  * [ARV09] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani.  Expander flows, geometric embeddings and graph partitioning.  J. ACM, 56(2), 2009.
  * [Bar15] Siddharth Barman.  Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory’s theorem.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 361–369, 2015.
  * [BCC+10] Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan.  Detecting high log-densities: an _O_(_n_ ${}^{\mbox{1/4}}$) approximation for densest _k_ -subgraph.  In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 201–210, 2010.
  * [BCG+12] Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou.  Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 388–405. SIAM, 2012.
  * [Ber45] Joseph Bertrand.  Memory on the number of values a function can take: when you swap the letters it contains.  Bachelor, 1845.
  * [BGH+15] Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer.  Making the long code shorter.  SIAM Journal on Computing, 44(5):1287–1324, 2015.
  * [BKRW17] Mark Braverman, Young Kun Ko, Aviad Rubinstein, and Omri Weinstein.  Eth hardness for densest-k-subgraph with perfect completeness.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1326–1341. SIAM, 2017.
  * [BKS19] Boaz Barak, Pravesh K. Kothari, and David Steurer.  Small-set expansion in shortcode graph and the 2-to-2 conjecture.  In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 9:1–9:12, 2019.
  * [Bol04] Béla Bollobás.  Extremal graph theory.  Courier Corporation, 2004.
  * [Cab13] Sergio Cabello.  Hardness of approximation for crossing number.  Discrete & Computational Geometry, 49(2):348–358, 2013.
  * [CCH+20] Shih-Chia Chang, Li-Hsuan Chen, Ling-Ju Hung, Shih-Shun Kao, and Ralf Klasing.  The hardness and approximation of the densest k-subgraph problem in parameterized metric graphs.  In 2020 International Computer Symposium (ICS), pages 126–130. IEEE, 2020.
  * [CDK+18] Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca.  The densest k-subhypergraph problem.  SIAM Journal on Discrete Mathematics, 32(2):1458–1477, 2018.
  * [Čeb50] Pafnutij Lvovič Čebyšev.  Mémoire sur les nombres premiers.  1850\.
  * [CH11] Markus Chimani and Petr Hliněnỳ.  A tighter insertion-based approximation of the crossing number.  In International Colloquium on Automata, Languages, and Programming, pages 122–134. Springer, 2011.
  * [Chu11] Julia Chuzhoy.  An algorithm for the graph crossing number problem.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 303–312. ACM, 2011.
  * [Chu15] Julia Chuzhoy.  Excluded grid theorem: Improved and simplified.  In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 645–654, 2015.
  * [CKN21] Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat.  Almost polynomial hardness of node-disjoint paths in grids.  Theory of Computing, 17(6):1–57, 2021.
  * [CMS11] Julia Chuzhoy, Yury Makarychev, and Anastasios Sidiropoulos.  On graph crossing number and edge planarization.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pages 1050–1069. SIAM, 2011.
  * [CMT20] Julia Chuzhoy, Sepideh Mahabadi, and Zihan Tan.  Towards better approximation of graph crossing number.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 73–84. IEEE, 2020.  Full version: Arxiv:2011.06545.
  * [CS13] Chandra Chekuri and Anastasios Sidiropoulos.  Approximation algorithms for euler genus and related problems.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 167–176. IEEE, 2013.
  * [CT22] Julia Chuzhoy and Zihan Tan.  A subpolynomial approximation algorithm for graph crossing number in low-degree graphs.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 303–316, 2022.  Full version: Arxiv:2202.06827.
  * [DKK+18a] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  On non-optimally expanding sets in Grassmann graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940–951, 2018.
  * [DKK+18b] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  Towards a proof of the 2-to-1 games conjecture?  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376–389, 2018.
  * [DP09] Devdatt P Dubhashi and Alessandro Panconesi.  Concentration of measure for the analysis of randomized algorithms.  Cambridge University Press, 2009.
  * [EGS02] Guy Even, Sudipto Guha, and Baruch Schieber.  Improved approximations of crossings in graph drawings and vlsi layout areas.  SIAM Journal on Computing, 32(1):231–252, 2002.
  * [Fei02] Uriel Feige.  Relations between average case complexity and approximation complexity.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 534–543, 2002.
  * [FL01] Uriel Feige and Michael Langberg.  Approximation algorithms for maximization problems arising in graph partitioning.  Journal of Algorithms, 41(2):174–211, 2001.
  * [FPK01] Uriel Feige, David Peleg, and Guy Kortsarz.  The dense k-subgraph problem.  Algorithmica, 29(3):410–421, 2001.
  * [FS+97] Uriel Feige, Michael Seltser, et al.  On the densest k-subgraph problem.  Technical Report CS97-16, Weizmann Institute of Science., 1997.  https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.9962&rep=rep1&type=pdf.
  * [GL09] Doron Goldstein and Michael Langberg.  The dense k subgraph problem.  arXiv preprint arXiv:0912.5327, 2009.
  * [Han22] Tesshu Hanaka.  Computing densest $k$-subgraph with structural parameters.  arXiv preprint arXiv:2207.09803, 2022.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM (JACM), 48(4):798–859, 2001.
  * [Kho02] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002.
  * [Kho06] Subhash Khot.  Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique.  SIAM Journal on Computing, 36(4):1025–1071, 2006.
  * [KLS00] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  Combinatorica, 20(3):393–415, 2000.
  * [KMMS18] Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra.  Small set expansion in the Johnson graph.  Electronic Colloquium on Computational Complexity (ECCC), 25:78, 2018.  https://eccc.weizmann.ac.il/report/2018/078.
  * [KMS17] Subhash Khot, Dor Minzer, and Muli Safra.  On independent sets, 2-to-2 games, and Grassmann graphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576–589, 2017.
  * [KMS18] Subhash Khot, Dor Minzer, and Muli Safra.  Pseudorandom sets in Grassmann graph have near-perfect expansion.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592–601, 2018\.
  * [KP93] G Kortsarz and D Peleg.  On choosing a dense subgraph.  In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 692–701. IEEE Computer Society, 1993.
  * [KS13] Subhash Khot and Muli Safra.  A two-prover one-round game with strong soundness.  Theory of Computing, 9:863–887, 2013.
  * [KS17] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.  Polylogarithmic approximation for minimum planarization (almost).  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 779–788, 2017.
  * [KS19] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.  Polylogarithmic approximation for euler genus on bounded degree graphs.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 164–175. ACM, 2019.
  * [Lei83] F. T. Leighton.  Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks.  MIT Press, 1983.
  * [Lin18] Bingkai Lin.  The parameterized complexity of the k-biclique problem.  Journal of the ACM (JACM), 65(5):1–23, 2018.
  * [LR99] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM (JACM), 46(6):787–832, 1999.
  * [LT79] Richard J Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [Man17] Pasin Manurangsi.  Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 954–961, 2017.
  * [Man18] Pasin Manurangsi.  Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis.  Algorithms, 11(1):10, 2018.
  * [Mat02] J. Matoušek.  Lectures on discrete geometry.  Springer-Verlag, 2002.
  * [PSS96] János Pach, Farhad Shahrokhi, and Mario Szegedy.  Applications of the crossing number.  Algorithmica, 16(1):111–117, 1996.
  * [PT00] J. Pach and G. Tóth.  Thirteen problems on crossing numbers.  Geombinatorics, 9(4):194–207, 2000.
  * [RS09] R. B. Richter and G. Salazar.  Crossing numbers.  In L. W. Beineke and R. J. Wilson, editors, Topics in Topological Graph Theory, chapter 7, pages 133–150. Cambridge University Press, 2009.
  * [Sch12] Marcus Schaefer.  The graph crossing number and its variants: A survey.  The electronic journal of combinatorics, pages DS21–Sep, 2012.
  * [Sot20] Renata Sotirov.  On solving the densest k-subgraph problem on large graphs.  Optimization Methods and Software, 35(6):1160–1178, 2020.
  * [Ste] David Steurer.  Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion.  Available at https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.189.5388&rep=rep1&type=pdf, 2010\.
  * [Tur77] P. Turán.  A note of welcome.  J. Graph Theory, 1:1–5, 1977.