# A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to
Hardness of Densest $k$-Subgraph and Other Problems

Julia Chuzhoy Toyota Technological Institute at Chicago. Email:
<EMAIL_ADDRESS>Supported in part by NSF grant CCF-2006464. Mina
Dalirrooyfard Massachusetts Institute of Technology. Email<EMAIL_ADDRESS>Part of the work was done while the author was a summer intern at TTIC. Vadim
Grinberg Weizmann Institute of Science. Email<EMAIL_ADDRESS>Zihan Tan DIMACS, Rutgers University. Email<EMAIL_ADDRESS>Supported
by a grant to DIMACS from the Simons Foundation (820931). Work done while the
author was a graduate student at University of Chicago.

We propose a new conjecture on hardness of low-degree $2$-CSP’s, and show that
new hardness of approximation results for Densest $k$-Subgraph and several
other problems, including a graph partitioning problem, and a variation of the
Graph Crossing Number problem, follow from this conjecture. The conjecture can
be viewed as occupying a middle ground between the $d$-to-$1$ conjecture, and
hardness results for $2$-CSP’s that can be obtained via standard techniques,
such as Parallel Repetition combined with standard $2$-prover protocols for
the 3SAT problem. We hope that this work will motivate further exploration of
hardness of $2$-CSP’s in the regimes arising from the conjecture. We believe
that a positive resolution of the conjecture will provide a good starting
point for further hardness of approximation proofs.

Another contribution of our work is proving that the problems that we consider
are roughly equivalent from the approximation perspective. Some of these
problems arose in previous work, from which it appeared that they may be
related to each other. We formalize this relationship in this work.

###### Contents

  1. 1 Introduction
    1. 1.1 A More Detailed Overview of our Results and Techniques
  2. 2 Preliminaries
    1. 2.1 General Notation
    2. 2.2 Problem Definitions and Additional Notation
    3. 2.3 Chernoff Bound
    4. 2.4 Auxiliary Lemma
  3. 3 Conditional Hardness of Densest $k$-Subgraph
    1. 3.1 Low-Degree CSP Conjecture
    2. 3.2 Conditional Hardness of Densest $k$-Subgraph
    3. 3.3 Proof of Theorem 3.7
    4. 3.4 Proof of Theorem 3.8
      1. 3.4.1 Step 1: Regularization
      2. 3.4.2 Step 2: Assignment Graph and Reduction to Bipartite Densest $(k_{1},k_{2})$-Subgraph
      3. 3.4.3 Step 3: Further Regularization
      4. 3.4.4 Step 4: Certifying that $H$ is a Good Graph or Computing a Subgraph of $H$
  4. 4 Reductions from Dense $k$-Coloring and (r,h)-Graph Partitioning to Densest $k$-Subgraph
    1. 4.1 An LP-Relaxation and Its Rounding
    2. 4.2 Approximately Solving the LP-Relaxation
  5. 5 Reductions from Densest $k$-Subgraph to Dense $k$-Coloring and (r,h)-Graph Partitioning
    1. 5.1 Auxiliary Graph $H$
    2. 5.2 Completing the Reduction from Densest $k$-Subgraph to Dense $k$-Coloring
    3. 5.3 Completing the Reduction from Densest $k$-Subgraph to (r,h)-Graph Partitioning
  6. 6 Reductions between (r,h)-Graph Partitioning and Maximum Bounded-Crossing Subgraph
    1. 6.1 Auxiliary Lemmas
    2. 6.2 Reduction from Maximum Bounded-Crossing Subgraph to (r,h)-Graph Partitioning: Proof of Theorem 6.1
    3. 6.3 Reduction from (r,h)-Graph Partitioning to Maximum Bounded-Crossing Subgraph– Proof of Theorem 6.2
      1. 6.3.1 Case 1: $C^{*}\geq 16n\alpha(n)\log^{7}n$
      2. 6.3.2 Case 2: $C^{*}<16n\alpha(n)\log^{7}n$
  7. 7 Acknowledgement
  8. A Proof of Lemma 2.1
    1. A.1 Reduction from Bipartite Densest $(k_{1},k_{2})$-Subgraph to Densest $k$-Subgraph
    2. A.2 Reduction from Densest $k$-Subgraph to Bipartite Densest $(k_{1},k_{2})$-Subgraph
  9. B Reduction from (r,h)-Graph Partitioning to Densest $k$-Subgraph
    1. B.1 Linear Programming Relaxation and an LP-Rounding Algortihm
    2. B.2 Approximately Solving the LP-Relaxation

##  1 Introduction

In this paper we consider several graph optimization problems, the most
prominent and extensively studied of which is Densest $k$-Subgraph. One of the
main motivations of this work is to advance our understanding of the
approximability of these problems. Towards this goal, we propose a new
conjecture on the hardness of a class of 2-CSP problems, that we call Low-
Degree CSP Conjecture, and we show that new hardness of approximation results
for all these problems follow from this conjecture. We believe that the
conjecture is interesting in its own right, as it can be seen as occupying a
middle ground between the $d$-to-$1$ conjecture, and the type of hardness of
approximation results that one can obtain for 2-CSP problems via standard
methods (such as using constant-factor hardness of approximation results for
3-SAT, combined with standard 2-prover protocols and Parallel Repetition).
While our conditional hardness of approximation proofs are combinatorial and
algorithmic in nature, we hope that this work will inspire complexity
theorists to study the conjecture, and also lead to other hardness of
approximation proofs that combine both combinatorial and algebraic techniques.

We prove a new conditional hardness of approximation result for Densest
$k$-Subgraph based on Low-Degree CSP Conjecture. In addition to the Densest
$k$-Subgraph problem, we study three other problems. The first problem, called
(r,h)-Graph Partitioning, recently arose in the hardness of approximation
proof of the Node-Disjoint Paths problem of [CKN21], who mention that the
problem appears similar to Densest $k$-Subgraph, but could not formalize this
intuition. We also study a new problem that we call Dense $k$-Coloring, that
can be viewed as a natural middle ground between Densest $k$-Subgraph and
(r,h)-Graph Partitioning. The fourth problem that we study is a variation of
the notoriously difficult Minimum Crossing Number problem, that we call
Maximum Bounded-Crossing Subgraph. This problem also arose implicitly in
[CKN21]. We show that all four problems are roughly equivalent from the
approximation perspective, in the regime where the approximation factors are
somewhat large (but some of our reductions require quasi-polynomial time). We
then derive conditional hardness of approximation results for all these
problems based on these reductions and the conditional hardness of Densest
$k$-Subgraph.

The main contribution of this paper is thus twofold: first, we propose a new
conjecture on hardness of CSP’s and show that a number of interesting hardness
of approximation results follow from it. Second, we establish a close
connection between the four problems that we study. The remainder of the
Introduction is organized as follows. We start by providing a brief overview
of the four problems that we study in this paper. We then state the Low-Degree
CSP Conjecture and put it into context with existing results and well-known
conjectures. Finally, we provide a more detailed overview of our results and
techniques.

##### Densest $k$-Subgraph.

In the Densest $k$-Subgraph problem, given an $n$-vertex graph $G$ and an
integer $k>1$, the goal is to compute a subset $S$ of $k$ vertices of $G$,
while maximizing the number of edges in $G[S]$. Densest $k$-Subgraph is one of
the most basic graph optimization problems that has been studied extensively
(see e.g. [KP93, FS+97, FPK01, FL01, Fei02, Kho06, GL09, BCC+10, AAM+11,
BCG+12, Bar15, BKRW17, Man17, CDK+18, Man18, Lin18, Sot20, CCH+20, Han22]). At
the same time it seems notoriously difficult, and despite this extensive work,
our understanding of its approximability is still incomplete. The best current
approximation algorithm for Densest $k$-Subgraph, due to [BCC+10], achieves,
for every $\varepsilon>0$, an $O(n^{1/4+\varepsilon})$-approximation, in time
$n^{O(1/\varepsilon)}$. Even though the problem appears to be very hard, its
hardness of approximation proof has been elusive. For example, no constant-
factor hardness of approximation proofs for Densest $k$-Subgraph are currently
known under the standard $\mbox{\sf P}\neq\mbox{\sf NP}$ assumption, or even
the stronger assumption that $\mbox{\sf NP}\not\subseteq\mbox{\sf
BPTIME}(n^{\textnormal{poly}\log n})$. In a breakthrough result, Khot [Kho06]
proved a factor-$c$ hardness of approximation for Densest $k$-Subgraph, for
some small constant $c$, assuming that $\mbox{\sf
NP}\not\subseteq\cap_{\varepsilon>0}\mbox{\sf BPTIME}(2^{n^{\varepsilon}})$.
Several other papers proved constant and super-constant hardness of
approximation results for Densest $k$-Subgraph under _average-case_ complexity
assumptions: namely that no efficient algorithm can refute random $3$-SAT or
random $k$-AND formulas [Fei02, AAM+11]. Additionally, a factor
$2^{\Omega(\log^{2/3}n)}$-hardness of approximation was shown under
assumptions on solving Planted Clique [AAM+11]. In a recent breakthrough,
Manurangsi [Man17] proved that, under the Exponential Time Hypothesis (ETH),
the Densest $k$-Subgraph problem is hard to approximate to within factor
$n^{1/(\log\log n)^{c}}$, for some constant $c$. Proving a super-constant
hardness of Densest $k$-Subgraph under weaker complexity assumptions remains a
tantalizing open question that we attempt to address in this paper.
Unfortunately, it seems unlikely that the techniques of [Man17] can yield such
a result. In this paper we show that, assuming the Low-Degree CSP Conjecture
that we introduce, Densest $k$-Subgraph is NP-hard to approximate to within
factor $2^{(\log n)^{\varepsilon}}$, for some constant $\varepsilon>0$.

##### The $(r,h)$-Graph Partitioning Problem.

A recent paper [CKN21] on the hardness of approximation of the Node-Disjoint
Paths (NDP) problem formulated and studied a new graph partitioning problem,
called (r,h)-Graph Partitioning. The input to the problem is a graph $G$, and
two integers, $r$ and $h$. The goal is to compute $r$ vertex-disjoint
subgraphs $H_{1},\ldots,H_{r}$ of $G$, such that for each $1\leq i\leq r$,
$|E(H_{i})|\leq h$, while maximizing $\sum_{i=1}^{r}|E(H_{i})|$. A convenient
intuitive way of thinking about this problem is that we are interested in
obtaining a balanced partition of the graph $G$ into $r$ vertex-disjoint
subgraphs, so that the subgraphs contain sufficiently many edges. Unlike
standard graph partitioning problems, that typically aim to minimize the
number of edges connecting the different subgraphs in the solution, our goal
is to maximize the total number of edges that are contained in the subgraphs.
In order to avoid trivial solutions, in which one of the subgraphs contains
almost the entire graph $G$, and the remaining subgraphs are almost empty, we
place an upper bound $h$ on the number of edges that each subgraph may
contribute towards the solution. Note that the subgraphs $H_{i}$ of $G$ in the
solution need not be vertex-induced subgraphs.

The work of [CKN21] attempted to use (r,h)-Graph Partitioning as a proxy
problem for proving hardness of approximation of NDP. Their results imply that
NDP is at least as hard to approximate as (r,h)-Graph Partitioning, to within
polylogarithmic factors. In order to prove hardness of NDP, it would then be
sufficient to show that (r,h)-Graph Partitioning is hard to approximate.
Unfortunately, [CKN21] were unable to do so. Instead, they considered a
generalization of (r,h)-Graph Partitioning, called (r,h)-Graph Partitioning
with Bundles. They showed that NDP is at least as hard as (r,h)-Graph
Partitioning with Bundles, and then proved hardness of this new problem. In
the (r,h)-Graph Partitioning with Bundles problem, the input is the same as in
(r,h)-Graph Partitioning, but now graph $G$ must be bipartite, and, for every
vertex $v$, we are given a partition ${\mathcal{B}}(v)$ of the set of edges
incident to $v$ into subsets that are called _bundles_. We require that, in a
solution $(H_{1},\ldots,H_{r})$ to the problem, for every vertex $v\in V(G)$,
and every bundle $\beta\in{\mathcal{B}}(v)$, at most one edge of $\beta$
contributes to the solution; in other words, at most one edge of $\beta$ may
lie in $\bigcup_{i}E(H_{i})$. This is a somewhat artificial problem, but this
definition allows one to bypass some of the barriers that arise when trying to
prove the hardness of (r,h)-Graph Partitioning from existing hardness results
for CSP’s.

It was noted in [CKN21] that the (r,h)-Graph Partitioning problem resembles
the Densest $k$-Subgraph problem for two reasons. First, in Densest
$k$-Subgraph, the goal is to compute a dense subgraph of a given graph, with a
prescribed number of vertices. One can think of (r,h)-Graph Partitioning as
the problem of computing many vertex-disjoint dense subgraphs of a given
graph. Second, natural hardness of approximation proofs for both problems seem
to run into the same barriers. It is therefore natural to ask: (i) Can we
prove that the (r,h)-Graph Partitioning problem itself is hard to approximate?
In particular, can the techniques of [CKN21] be exploited in order to obtain
such a proof? and (ii) Can we formalize this intuitive connection between
(r,h)-Graph Partitioning and Densest $k$-Subgraph? In this paper we make
progress on both these questions. Our conditional hardness result for Densest
$k$-Subgraph indeed builds on the ideas from [CKN21] for proving hardness of
(r,h)-Graph Partitioning with Bundles. We also provide “almost” approximation-
preserving reductions between (r,h)-Graph Partitioning to Densest
$k$-Subgraph: we show that, if there is an efficient factor
$\alpha(n)$-approximation algorithm for Densest $k$-Subgraph, then there is a
randomized efficient factor $O(\alpha(n^{2})\cdot\textnormal{poly}\log
n)$-approximation algorithm to (r,h)-Graph Partitioning. We also provide a
reduction in the opposite direction: we prove that, if there is an efficient
$\alpha(n)$-approximation algorithm for (r,h)-Graph Partitioning, then there
is a randomized algorithm for Densest $k$-Subgraph, that achieves
approximation factor $O\left((\alpha(n^{O(\log
n)}))^{3}\cdot\log^{2}n\right)$, in time $n^{O(\log n)}$. Therefore, we prove
that Densest $k$-Subgraph and (r,h)-Graph Partitioning are roughly equivalent
from the approximation perspective (at least for large approximation factors
and quasi-polynomial running times). Combined with our conditional hardness of
approximation for Densest $k$-Subgraph, our results show that, assuming the
Low-Degree CSP Conjecture, for some constant $0<\varepsilon\leq 1/2$, there is
no efficient $2^{(\log n)^{\varepsilon}}$-approximation algorithm for
(r,h)-Graph Partitioning, unless $\mbox{\sf NP}\subseteq\mbox{\sf
BPTIME}(n^{O(\log n)})$.

##### Maximum Bounded-Crossing Subgraph.

The third problem that we study is a variation of the classical Minimum
Crossing Number problem. In the Minimum Crossing Number problem, given an
input $n$-vertex graph $G$, the goal is to compute a drawing of $G$ in the
plane while minimizing the number of crossings in the drawing. We define the
notions of graph drawing and crossings formally in the Preliminaries, but
these notions are quite intuitive and the specifics of the definition are not
important in this high-level overview.

The Minimum Crossing Number problem was initially introduced by Turán [Tur77]
in 1944, and has been extensively studied since then (see, e.g., [Chu11,
CMS11, CH11, CS13, KS17, KS19, CMT20], and also [RS09, PT00, Mat02, Sch12] for
excellent surveys). But despite all this work, most aspects of the problem are
still poorly understood. A long line of work [LR99, EGS02, CMS11, Chu11, KS17,
KS19, Chu15, CT22] has recently led to the first sub-polynomial approximation
algorithm for the problem in _low degree graphs_. Specifically, [CT22] obtain
a factor $O\left(2^{O((\log n)^{7/8}\log\log
n)}\cdot\Delta^{O(1)}\right)$-approximation algorithm for Minimum Crossing
Number, where $\Delta$ is the maximum vertex degree. To the best of our
knowledge, no non-trivial approximation algorithms are known for the problem
when vertex degrees in the input graph $G$ can be arbitrary. However, on the
negative side, only APX-hardness is known for the problem [Cab13, AMS07]. As
the current understanding of the Minimum Crossing Number problem from the
approximation perspective is extremely poor, it is natural to study hardness
of approximation of its variants.

Let us consider two extreme variations of the Minimum Crossing Number problem.
The first variant is the Minimum Crossing Number problem itself, where we need
to draw an input graph $G$ in the plane with fewest crossings. The second
variant is where we need to compute a subgraph $G^{\prime}$ of the input graph
$G$ that is planar, while maximizing $|E(G^{\prime})|$. The latter problem has
a simple constant-factor approximation algorithm, obtained by letting
$G^{\prime}$ be any spanning forest of $G$ (this is since a planar $n$-vertex
graph may only have $O(n)$ edges).

In this paper we study a variation of the Minimum Crossing Number problem,
that we call Maximum Bounded-Crossing Subgraph, which can be viewed as an
intermediate problem between these two extremes. In the Maximum Bounded-
Crossing Subgraph problem, given an $n$-vertex graph $G$ and an integer $L>0$,
the goal is to compute a subgraph $H\subseteq G$, such that $H$ has a plane
drawing with at most $L$ crossings, while maximizing $|E(H)|$. This problem is
only interesting when the bound $L$ on the number of crossings is $\Omega(n)$.
This is since, from the Crossing Number Inequality [ACNS82, Lei83], if
$|E(G)|\geq 4|V(G)|$, then the crossing number of $G$ is at least
$\Omega(|E(G)|^{3}/|V(G)|^{2})$. Therefore, for $L=O(n)$, a spanning tree
provides a constant-factor approximation to the problem. We emphasize that the
focus here is on dense graphs, whose crossing number may be as large as
$\Omega(n^{4})$.

The Maximum Bounded-Crossing Subgraph problem was implicitly used in [CKN21]
for proving hardness of approximation of NDP, as an intermediate problem, in
the reduction from (r,h)-Graph Partitioning with Bundles to NDP. Their work
suggests that there may be a connection between (r,h)-Graph Partitioning and
Maximum Bounded-Crossing Subgraph, even though the two problems appear quite
different. In this paper we prove that the two problems are roughly equivalent
from the approximation perspective: if there is an efficient factor
$\alpha(n)$-approximation algorithm for (r,h)-Graph Partitioning, then there
is an efficient $O(\alpha(n)\cdot\textnormal{poly}\log n)$-approximation
algorithm for Maximum Bounded-Crossing Subgraph. On the other hand, an
efficient $\alpha(n)$-approximation algorithm for Maximum Bounded-Crossing
Subgraph implies an efficient $O((\alpha(n))^{2}\cdot\textnormal{poly}\log
n)$-approximation algorithm for (r,h)-Graph Partitioning. Combined with our
conditional hardness of approximation for (r,h)-Graph Partitioning, we get
that, assuming the Low-Degree CSP Conjecture, for some constant
$0<\varepsilon\leq 1/2$ there is no efficient $2^{(\log
n)^{\varepsilon}}$-approximation algorithm for Maximum Bounded-Crossing
Subgraph, unless $\mbox{\sf NP}\subseteq\mbox{\sf BPTIME}(n^{O(\log n)})$.

##### Dense $k$-Coloring.

The fourth and last problem that we consider is Dense $k$-Coloring. In this
problem, the input is an $n$-vertex graph $G$ and an integer $k$, such that
$n$ is an integral multiple of $k$. The goal is to partition $V(G)$ into $n/k$
disjoint subsets $S_{1},\ldots,S_{n/k}$, of cardinality $k$ each, so as to
maximize $\sum_{i=1}^{n/k}|E(S_{i})|$. This problem can be viewed as an
intermediate problem between Densest $k$-Subgraph and (r,h)-Graph
Partitioning. The connection to (r,h)-Graph Partitioning seems clear: in both
problems, the goal is to compute a large collection of subgraphs of the input
graph $G$, that contain many edges of $G$. While in (r,h)-Graph Partitioning
we place a limit on the number of edges in each subgraph, in Dense
$k$-Coloring we require that each subgraph contains exactly $k$ vertices. The
connection to the Densest $k$-Subgraph problem is also clear: while in Densest
$k$-Subgraph the goal is to compute a single dense subgraph of $G$ containing
$k$ vertices, in Dense $k$-Coloring we need to partition $G$ into many dense
subgraphs, containing $k$ vertices each. We show reductions between the Dense
$k$-Coloring and the Densest $k$-Subgraph problem in both directions, that
provide very similar guarantees to the reductions between (r,h)-Graph
Partitioning and Densest $k$-Subgraph. In particular, our results show that,
assuming the Low-Degree CSP Conjecture, for some constant $0<\varepsilon\leq
1/2$, there is no efficient $2^{(\log n)^{\varepsilon}}$-approximation
algorithm for Dense $k$-Coloring, unless $\mbox{\sf NP}\subseteq\mbox{\sf
BPTIME}(n^{O(\log n)})$.

##### The Low-Degree CSP Conjecture.

We now turn to describe our new conjecture on the hardness of 2-CSP’s. We
consider the following bipartite version of the Constraint Satisfaction
Problem with 2 variables per constraint (2-CSP). The input consists of two
sets $X$ and $Y$ of variables, together with an integer $A\geq 1$. Every
variable in $X\cup Y$ takes values in $[A]=\\{1,\ldots,A\\}$. We are also
given a collection $\mathcal{C}$ of constraints, where each constraint
$C(x,y)\in\mathcal{C}$ is defined over a pair of variables $x\in X$ and $y\in
Y$. For each such constraint, we are given a truth table that, for every pair
of assignments $a$ to $x$ and $a^{\prime}$ to $y$, specifies whether
$(a,a^{\prime})$ _satisfy_ the constraint. The _value_ of the CSP is the
largest fraction of constraints that can be simultaneously satisfied by an
assignment to the variables. For given values $0<s<c\leq 1$, the $(c,s)$-Gap-
CSP problem is the problem of distinguishing CSP’s of value at least $c$ from
those of value at most $s$.

We can associate, to each constraint $C=C(x,y)\in\mathcal{C}$, a bipartite
graph $G_{C}=(L,R,E)$, where $L=R=[A]$, and there is an edge $(a,a^{\prime})$
in $E$ iff the assignments $a$ to $x$ and $a^{\prime}$ to $y$ satisfy $C$.
Notice that instance ${\mathcal{I}}$ of the Bipartite 2-CSP problem is
completely defined by $X,Y,A,\mathcal{C}$, and the graphs in
$\\{G_{C}\\}_{C\in\mathcal{C}}$, so we will denote
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$. We let the
_size_ of instance ${\mathcal{I}}$ be
$\operatorname{size}({\mathcal{I}})=|\mathcal{C}|\cdot A^{2}+|X|+|Y|$. We
sometimes refer to $A$ as the _size of the alphabet for instance
${\mathcal{I}}$_. We say that instance ${\mathcal{I}}$ of 2-CSP is _$d$
-to-$d^{\prime}$_ iff for every constraint $C$, every vertex of $G_{C}$ that
lies in $L$ has degree at most $d$, and every vertex that lies in $R$ has
degree at most $d^{\prime}$. (We note that this is somewhat different from the
standard definition, that requires that all vertices in $L$ have degree
exactly $d$ and all vertices of $R$ have degree exactly $d^{\prime}$. In the
standard definition, the alphabet sizes for variables in $X$ and $Y$ may be
different, that is, variables in $X$ take values in $[A]$ and variables of $Y$
take values in $[A^{\prime}]$ for some integers $A,A^{\prime}$. However, this
difference is insignificant to our discussion, and it is more convenient for
us to use this slight variation of the standard definition).

The famous Unique-Games Conjecture of Khot [Kho02] applies to $1$-to-$1$
CSP’s. The conjecture states that, for any $0<\varepsilon<1$, there is a large
enough value $A$, such that the $(1-\varepsilon,\varepsilon)$-Gap-CSP problem
is NP-hard for $1$-to-$1$ instances with alphabet size $A$. The conjecture
currently remains open, though interesting progress has been made on the
algorithmic side: the results of [ABS15] provide an algorithm for the problem
with running time $2^{n^{O(1/\varepsilon^{1/3})}}$.

A conjecture that is closely related to the Unique-Games Conjecture is the
$d$-to-$1$ Conjecture of Khot [Kho02]. The conjecture states that, for every
$0<\varepsilon<1$, and $d>0$, there is a large enough value $A$, such that the
$(1,\varepsilon)$-Gap-CSP problem in $d$-to-$1$ instances with alphabet size
$A$ is NP-hard.

Håstad [Hås01] proved the following nearly optimal hardness of approximation
results for CSP’s: he showed that for every $0<\varepsilon<1$, there are
values $d$ and $A$, such that the problem of $(1,\varepsilon)$-Gap-CSP in
$d$-to-$1$ instances with alphabet size $A$ is NP-hard. The value $d$,
however, depends exponentially on $\textnormal{poly}(1/\varepsilon)$ in this
result. In contrast, in the $d$-to-$1$ Conjecture, both $d$ and $\varepsilon$
are fixed, and $d$ may not have such a strong dependence on $1/\varepsilon$.

On the algorithmic side, the results of [ABS15, Ste] provide an algorithm for
$(c,s)$-Gap-CSP on $d$-to-$1$ instances. The running time of the algorithm is
$2^{n^{O(1/(\log(1/s))^{1/2})}}$, where the $O(\cdot)$ notation hides factors
that are polynomial in $d$ and $A$.

A recent breakthrough in this area is the proof of the $2$-to-$2$ conjecture
(now theorem), that builds on a long sequence of work [BGH+15, KS13, KMMS18,
BKS19, KMS17, DKK+18a, DKK+18b, KMS18]. The theorem proves that for every
$0<\varepsilon<1$, there is a large enough value $A$, such that the
$(1-\varepsilon,\varepsilon)$-Gap-CSP problem is NP-hard on $2$-to-$2$
instances with alphabet size $A$.

In this paper, we propose the following conjecture, that we refer to as _Low-
Degree CSP Conjecture_ , regarding the hardness of Gap-CSP in $d$-to-$d$
instances.

######  Conjecture 1 (Low-Degree CSP Conjecture).

There is a constant $0<\varepsilon\leq 1/2$, such that it is NP-hard to
distinguish between $d(n)$-to-$d(n)$ instances of 2-CSP of size $n$, that have
value at least $1/2$, and those of value at most $s(n)$, where $d(n)=2^{(\log
n)^{\varepsilon}}$ and $s(n)=1/2^{64(\log n)^{1/2+\varepsilon}}$.

We now compare this conjecture to existing conjectures and results in this
area that we are aware of. First, in contrast to the $d$-to-$1$ conjecture, we
allow the parameter $d$ and the soundness parameter $s$ to be functions of $n$
– the size of the input instance. Note that the size of the input instance
depends on the alphabet size $A$, so, unlike in the setting of the $d$-to-$1$
conjecture, $A$ may no longer be arbitrarily large compared to $d$ and $s$.

The hardness of approximation result of Håstad [Hås01] for $d$-to-$d$ CSP’s
only holds when $d$ depends exponentially on $\textnormal{poly}(1/s)$, (in
particular it may not extend to the setting where $s(n)=1/2^{64(\log
n)^{1/2+\varepsilon}}$, since the size $n$ of the instance depends
polynomially on $d(n)$).

We can also combine standard constant hardness of approximation results for
CSP’s (such as, for example, $3$-SAT) with the Parallel Repetition theorem, to
obtain NP-hardness of $(1,s(n))$-Gap-CSP on $d(n)$-to-$d(n)$ instances. Using
this approach, if we start from an instance of CSP of size $N$ and a constant
hardness gap (with perfect completeness), after $\ell$ rounds of parallel
repetition, we obtain hardness of $(1,s)$-Gap-CSP on $d$-to-$d$ instances with
$s=2^{O(\ell)}$, $d=2^{O(\ell)}$, and the resulting instance size
$n=N^{O(\ell)}$. By setting the number of repetition to be
$\ell=\Theta\left((\log N)^{(1/2+\varepsilon)/(1/2-\varepsilon)}\right)$, we
can ensure the desired bound $s(n)=1/2^{64(\log n)^{1/2+\varepsilon}}$.
However, in this setting, we also get that $d(n)=2^{\Omega((\log
n)^{1/2+\varepsilon})}$, which is significantly higher than the desired value
$d(n)=2^{(\log n)^{\varepsilon}}$.

Lastly, one could attempt to combine the recent proof of the $2$-to-$2$
conjecture with Parallel Repetition in order to reap the benefits of both
approaches, but the resulting parameters also fall short of the ones stated in
the conjecture.

From the above discussion, one can view the Low-Degree CSP Conjecture as
occupying a middle ground between the $d$-to-$1$ conjecture, and the results
one can obtain via standard techniques of amplifying a constant hardness of a
CSP, such as 3SAT, via Parallel Repetition.

We now proceed to discuss our results and techniques in more detail.

###  1.1 A More Detailed Overview of our Results and Techniques

In addition to posing the Low-Degree CSP Conjecture that we already described
above, we prove conditional hardness of approximation of the four problems
that we consider. We also prove that all four problems are roughly equivalent
approximation-wise. We now discuss the conditional hardness of approximation
for Densest $k$-Subgraph and the connections between the four problems that we
establish.

##### Conditional Hardness of Densest $k$-Subgraph.

Our first result is a conditional hardness of Densest $k$-Subgraph.
Specifically, we prove that, assuming 1 holds and $\mbox{\sf P}\neq\mbox{\sf
NP}$, for some $0<\varepsilon\leq 1/2$, there is no efficient approximation
algorithm for Densest $k$-Subgraph problem that achieves approximation factor
$2^{(\log N)^{\varepsilon}}$, where $N$ is the number of vertices in the input
graph.

We now provide a brief overview of our techniques. The proof of the above
result employs a Cook-type reduction, and follows some of the ideas that were
introduced in [CKN21]. We assume for contradiction that there is a
factor-$\alpha$ algorithm ${\mathcal{A}}$ for the Densest $k$-Subgraph
problem, where $\alpha=2^{(\log N)^{\varepsilon}}$. Given an input instance
${\mathcal{I}}$ of the $2$-CSP problem of size $n$, that is a $d(n)$-to-$d(n)$
instance, we construct a constraint graph $H$ representing ${\mathcal{I}}$. We
gradually decompose graph $H$ into a collection ${\mathcal{H}}$ of disjoint
subgraphs, such that, for each subgraph $H^{\prime}\in{\mathcal{H}}$, we can
either certify that the value of the corresponding instance of $2$-CSP is at
most $1/4$, or it is at least $\beta$, for some carefully chosen parameter
$\beta$. In order to compute the decomposition, we start with
${\mathcal{H}}=\\{H\\}$. If, for a graph $H^{\prime}\in{\mathcal{H}}$, we
certified that the corresponding instance of $2$-CSP has value at most $1/4$,
or at least $\beta$, then we say that graph $H^{\prime}$ is _inactive_.
Otherwise, we say that it is _active_. As long as ${\mathcal{H}}$ contains at
least one active graph, we perform iterations. In each iteration, we select an
arbitrary graph $H^{\prime}\in{\mathcal{H}}$ to process. In order to process
$H^{\prime}$, we consider an _assignment graph_ $G^{\prime}$ associated with
$H^{\prime}$, that contains a vertex for every variable-assignment pair
$(x,a)$, where $x$ is a variable whose corresponding vertex belongs to
$H^{\prime}$. We view $G^{\prime}$ as an instance of the Densest $k$-Subgraph
problem, for an appropriately chosen parameter $k$, and apply the
approximation algorithm ${\mathcal{A}}$ for Densest $k$-Subgraph to it. Let
$S$ be the set of vertices of $G^{\prime}$ that Algorithm ${\mathcal{A}}$
computes as a solution to this instance. We exploit the set $S$ of vertices in
order to either (i) compute a large subset $E^{\prime}\subseteq E(H^{\prime})$
of edges, such that, if we denote by
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$ the set of constraints
corresponding to $E^{\prime}$, then at most $1/4$ of the constraints of
$\mathcal{C}^{\prime}$ can be simultaneously satisfied; or (ii) compute a
large subset $E^{\prime}\subseteq E(H^{\prime})$ of edges as above, and
certify that at least a $\beta$-fraction of such constraints can be satisfied;
or (iii) compute a subgraph $H^{\prime\prime}\subseteq H^{\prime}$, such that
$|V(H^{\prime\prime})|\ll|V(H^{\prime})|$, and the number of edges contained
in graphs $H^{\prime\prime}$ and $H^{\prime}\setminus V(H^{\prime\prime})$ is
sufficiently large compared to $E(H^{\prime})$. In the former two cases, we
replace $H^{\prime}$ with graph $H^{\prime}[E^{\prime}]$ in ${\mathcal{H}}$,
and graph $H^{\prime}[E^{\prime}]$ becomes inactive. In the latter case, we
replace $H^{\prime}$ with two graphs: $H^{\prime\prime}$ and
$H^{\prime}\setminus V(H^{\prime\prime})$, that both remain active. The
algorithm terminates once every graph in ${\mathcal{H}}$ is inactive. The crux
of the analysis of the algorithm is to show that, when the algorithm
terminates, the total number of edges lying in the subgraphs
$H^{\prime}\in{\mathcal{H}}$ is high, compared to $|E(H)|$. This algorithm for
decomposing graph $H$ into subgraphs and its analysis employ some of the
techniques and ideas introduced in [CKN21], and is very similar in spirit to
the hardness of approximation proof of the (r,h)-Graph Partitioning with
Bundles problem, though details are different. We employ this decomposition
algorithm multiple times, in order to obtain a partition
$(E_{0},E_{1},\ldots,E_{z})$ of the set $E(H)$ of edges into a small number of
subsets, such that, among the constraints corresponding to the edges of
$E_{0}$, at most a $1/4$-fraction can be satisfied by any assignment to $X\cup
Y$, and, for all $1\leq i\leq z$, a large fraction of constraints
corresponding to edges of $E_{i}$ can be satisfied by some assignment.
Depending on the cardinality of the set $E_{0}$ of edges we then determine
whether ${\mathcal{I}}$ is a Yes-Instance or a No-Instance.

##### Reductions from Dense $k$-Coloring and (r,h)-Graph Partitioning to
Densest $k$-Subgraph.

We show that, if there is an efficient factor $\alpha(n)$-approximation
algorithm for the Densest $k$-Subgraph problem, then there is an efficient
$O(\alpha(n^{2})\cdot\textnormal{poly}\log n)$-approximation algorithm for
Dense $k$-Coloring, and an efficient
$O(\alpha(n^{2})\cdot\textnormal{poly}\log n)$-approximation algorithm for
(r,h)-Graph Partitioning. The two reductions are very similar, so we focus on
describing the first one. We believe that the reduction is of independent
interest, and uses unusual techniques.

We assume that there is an $\alpha(n)$-approximation algorithm for the Densest
$k$-Subgraph problem. In order to obtain an approximation algorithm for Dense
$k$-Coloring, we start by formulating a natural LP-relaxation for the problem.
Unfortunately, this LP-relaxation has a large number of variables: roughly
$n^{\Theta(k)}$, where $n$ is the number of vertices in the input graph and
$k$ is the parameter of the Dense $k$-Coloring problem instance. We then show
an efficient algorithm, that, given a solution to the LP-relaxation, whose
support size is bounded by $\textnormal{poly}(n)$, computes an approximate
integral solution to the Dense $k$-Coloring problem.

The main challenge is that, since the LP relaxation has $n^{\Theta(k)}$
variables, it is unclear how to solve it efficiently. We consider the dual
linear program, that has $\textnormal{poly}(n)$ variables and $n^{\Theta(k)}$
constraints. Using the $\alpha(n)$-approximation algorithm for Densest
$k$-Subgraph as a subroutine, we design an approximate separation oracle for
the dual LP, that allows us to solve the original LP-relaxation for Dense
$k$-Coloring, obtaining a solution whose support size is bounded by
$\textnormal{poly}(n)$. By applying the LP-rounding approximation algorithm to
this solution, we obtain the desired approximate solution to the input
instance of Dense $k$-Coloring.

##### Reductions from Densest $k$-Subgraph to (r,h)-Graph Partitioning and
Dense $k$-Coloring.

We prove that, if there is an efficient $\alpha(n)$-approximation algorithm
for Dense $k$-Coloring, then there is a randomized algorithm for the Densest
$k$-Subgraph problem, whose running time is $n^{O(\log n)}$, that with high
probability obtains an $O(\alpha(n^{O(\log n)})\cdot\log n)$-approximate
solution to the input instance of the problem. We also show a similar
reduction from Densest $k$-Subgraph to (r,h)-Graph Partitioning, but now the
resulting approximation factor for Densest $k$-Subgraph becomes
$O((\alpha(n^{O(\log N)}))^{3}\cdot\log^{2}n)$. By combining these reductions
with our conditional hardness result for Densest $k$-Subgraph, we get that,
assuming the Low-Degree CSP Conjecture, for some constant $0<\varepsilon\leq
1/2$, there is no efficient $2^{(\log n)^{\varepsilon}}$-approximation
algorithm for (r,h)-Graph Partitioning and for Dense $k$-Coloring, unless
$\mbox{\sf NP}\subseteq\mbox{\sf BPTIME}(n^{O(\log n)})$.

The two reductions are very similar; we focus on the reduction to Dense
$k$-Coloring in this overview. Our construction is inspired by the results of
[KLS00], and we borrow some of our ideas from them. Assume that there is an
efficient $\alpha(n)$-approximation algorithm for Dense $k$-Coloring. Let $G$
be an instance of the Densest $k$-Subgraph problem. The main difficulty in the
reduction is that it is possible that $G$ only contains one very dense
subgraph induced by $k$ vertices, while the Dense $k$-Coloring problem
requires that the input graph $G$ can essentially be partitioned into many
such dense subgraphs. To overcome this difficulty, we construct a random
“inflated” bipartite graph $H$, that contains $n^{O(\log n)}$ vertices, where
$n=|V(G)|$. Every vertex of $G$ is mapped to some vertex of $H$ at random,
while every edge of $G$ is mapped to a large number of edges of $H$. This
allows us to ensure that, if $G$ contains a subgraph $G^{\prime}$ induced by a
set of $k$ vertices, where $|E(G^{\prime})|=R$, then graph $H$ can essentially
be partitioned into a large number of subgraphs that contain $k$ vertices
each, and many of them contain close to $R$ edges. Therefore, we can apply our
$\alpha(n)$-approximation algorithm for Dense $k$-Coloring to the new graph
$H$. The main challenge in the reduction is that, while this approximation
algorithm is guaranteed to return a large number of disjoint dense subgraphs
of $H$, since every edge of $G$ contributes many copies to $H$, it is not
clear that one can extract a single dense subgraph of $G$ from dense subgraphs
of $H$. The main difficulty in the reduction is to ensure that, on the one
hand, a single $k$-vertex dense subgraph in $G$ can be translated into
$|V(H)|/k$ dense subgraphs of $H$; and, on the other hand, a dense $k$-vertex
subgraph of $H$ can be translated into a dense subgraph of $G$ on $k$
vertices. We build on and expand the ideas from [KLS00] in order to ensure
these properties.

##### Reductions between (r,h)-Graph Partitioning and Maximum Bounded-Crossing
Subgraph.

Lastly, we provide reductions between (r,h)-Graph Partitioning and Maximum
Bounded-Crossing Subgraph in both directions. First, we show that, if there is
an efficient factor $\alpha(n)$-approximation algorithm for (r,h)-Graph
Partitioning, then there is an efficient
$O(\alpha(n)\cdot\textnormal{poly}\log n)$-approximation algorithm for Maximum
Bounded-Crossing Subgraph. On the other hand, an efficient
$\alpha(n)$-approximation algorithm for Maximum Bounded-Crossing Subgraph
implies an efficient $O((\alpha(n))^{2}\cdot\textnormal{poly}\log
n)$-approximation algorithm for (r,h)-Graph Partitioning. Combined with our
conditional hardness of approximation for (r,h)-Graph Partitioning, we get
that, assuming the Low-Degree CSP Conjecture, for some constant
$0<\varepsilon\leq 1/2$, there is no efficient $2^{(\log
n)^{\varepsilon}}$-approximation algorithm for (r,h)-Graph Partitioning,
unless $\mbox{\sf NP}\subseteq\mbox{\sf BPTIME}(n^{O(\log n)})$.

Both these reductions exploit the following connection between crossing number
and graph partitioning: if a graph $G$ has a drawing with at most $L$
crossings, then there is a balanced cut in $G$, containing at most
$O\left(\sqrt{L+\Delta\cdot|E(G)|}\right)$ edges, where $\Delta$ is maximum
vertex degree in $G$. This result can be viewed as an extension of the
classical Planar Separator Theorem of [LT79]. Another useful fact exploited in
both reductions is that any graph $G$ with $m$ edges has a plane drawing with
at most $m^{2}$ crossings. In particular, if
${\mathcal{H}}=\\{H_{1},\ldots,H_{r}\\}$ is a solution to an instance of the
(r,h)-Graph Partitioning problem on graph $G$, then there is a drawing of
graph $H=\bigcup_{i=1}^{r}H_{i}$, in which the number of crossings is bounded
by $r\cdot h^{2}$. These two facts establish a close relationship between the
(r,h)-Graph Partitioning and Maximum Bounded-Crossing Subgraph problems, that
are exploited in both our reductions.

We have now obtained a chain of reductions that show that all four problems,
Densest $k$-Subgraph, Dense $k$-Coloring, (r,h)-Graph Partitioning, and
Maximum Bounded-Crossing Subgraph are almost equivalent from approximation
viewpoint (if one considers sufficiently large approximation factors, and
allows randomized quasi-polynomial time algorithms). We also obtain
conditional hardness of approximation results for all four problems based on
the Low-Degree CSP Conjecture.

##### Organization.

We start with preliminaries in Section 2. In Section 3 we provide the
conditional hardness of approximation proof for the Densest $k$-Subgraph
problem. In Section 4 we provide our reductions from Dense $k$-Coloring and
(r,h)-Graph Partitioning to Densest $k$-Subgraph, and in Section 5 we provide
reductions in the opposite direction. Lastly in Section 6 we provide
reductions between (r,h)-Graph Partitioning and Maximum Bounded-Crossing
Subgraph.

##  2 Preliminaries

By default, all logarithms are to the base of $2$. For a positive integer $N$,
we denote by $[N]=\\{1,2,\ldots,N\\}$. All graphs are finite, simple and
undirected. We say that an event holds with high probability if the
probability of the event is $1-1/n^{c}$ for a large enough constant $c$, where
$n$ is the number of vertices in the input graph.

###  2.1 General Notation

Let $G$ be a graph and let $S$ be a subset of its vertices. We denote by
$G[S]$ the subgraph of $G$ induced by $S$. For two disjoint subsets $A,B$ of
vertices of $G$, we denote by $E_{G}(A,B)$ the set of all edges with one
endpoint in $A$ and the other endpoint in $B$, and we denote by $E_{G}(A)$ the
set of all edges with both endpoints in $A$. Given a graph $G$ and a vertex
$v\in V(G)$, we denote by $\deg_{G}(v)$ the degree of $v$ in $G$. For a subset
$S$ of vertices of $G$, its _volume_ is $\operatorname{vol}_{G}(S)=\sum_{v\in
S}\deg_{G}(v)$. We sometimes omit the subscript $G$ if it is clear from the
context.

Given a graph $G$, a drawing $\varphi$ of $G$ is an embedding of $G$ into the
plane, that maps every vertex $v$ of $G$ to a point (called the _image of $v$_
and denoted by $\varphi(v)$), and every edge $e$ of $G$ to a simple curve
(called the _image of $e$_ and denoted by $\varphi(e)$), that connects the
images of its endpoints. If $e$ is an edge of $G$ and $v$ is a vertex of $G$,
then the image of $e$ may only contain the image of $v$ if $v$ is an endpoint
of $e$. Furthermore, if some point $p$ belongs to the images of three or more
edges of $G$, then $p$ must be the image of a common endpoint of all edges $e$
with $p\in\varphi(e)$. We say that two edges $e,e^{\prime}$ of $G$ _cross_ at
a point $p$, if $p\in\varphi(e)\cap\varphi(e^{\prime})$, and $p$ is not the
image of a shared endpoint of these edges. Given a graph $G$ and a drawing
$\varphi$ of $G$ in the plane, we use $\mathsf{cr}(\varphi)$ to denote the
number of crossings in $\varphi$, and the crossing number of $G$, denoted by
$\mathsf{CrN}(G)$, is the minimum number of crossings in any drawing of $G$.

###  2.2 Problem Definitions and Additional Notation

In this paper we consider the following four problems: Densest $k$-Subgraph,
Dense $k$-Coloring, (r,h)-Graph Partitioning and Maximum Bounded-Crossing
Subgraph. We now define the problems, along with some additional notation.

##### Densest $k$-Subgraph.

In the Densest $k$-Subgraph problem, the input is a graph $G$ and an integer
$k>0$. The goal is to compute a subset $S\subseteq V(G)$ of $k$ vertices,
maximizing $|E_{G}(S)|$. We denote an instance of the problem by
$\mathrm{DkS}(G,k)$, and we denote the value of the optimal solution to
instance $\mathrm{DkS}(G,k)$ by $\mathrm{OPT_{DkS}}(G,k)$.

We also consider a bipartite version of the Densest $k$-Subgraph problem,
called
Bipartite Densest $(k_{1},k_{2})$-Subgraph. This problem was first studied in
[AAM+11]. The input to the problem is a bipartite graph $G=(A,B,E)$ and
positive integers $k_{1},k_{2}$. The goal is to compute a subset $S\subseteq
V(G)$ of vertices with $|S\cap A|=k_{1}$ and $|S\cap B|=k_{2}$, such that
$|E_{G}(S)|$ is maximized. An instance of this problem is denoted by
$\mathrm{BDkS}(G,k_{1},k_{2})$, and the value of the optimal solution to
instance $\mathrm{BDkS}(G,k_{1},k_{2})$ is denoted by
$\mathrm{OPT_{BDkS}}(G,k_{1},k_{2})$. The following lemma shows that the
Bipartite Densest $(k_{1},k_{2})$-Subgraph problem and the Densest
$k$-Subgraph problem are roughly equivalent from the approximation viewpoint.
Similar results were also shown in prior work. For completeness, we provide
the proof in Appendix A.

######  Lemma 2.1.

Let $\alpha:\mathbb{Z^{+}}\to\mathbb{Z^{+}}$ be an increasing function such
that $\alpha(n)=o(n)$. Then the following hold:

  * •

If there exists an $\alpha(n)$-approximation algorithm for the Densest
$k$-Subgraph problem with running time at most $T(n)$, where $n$ is the number
of vertices in the input graph, then there exists an
$O(\alpha(N^{2}))$-approximation algorithm for the Bipartite Densest
$(k_{1},k_{2})$-Subgraph problem, with running time
$O(T(N^{2})\cdot\textnormal{poly}(N))$, where $N$ is the number of vertices in
the input graph. Moreover, if the algorithm for Densest $k$-Subgraph is
deterministic, then so is the algorithm for Bipartite Densest
$(k_{1},k_{2})$-Subgraph.

  * •

Similarly, if there exists an efficient $\alpha(N)$-approximation algorithm
for the Bipartite Densest $(k_{1},k_{2})$-Subgraph problem, where $N$ is the
number of vertices in the input graph, then 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. Moreover, if the
algorithm for Bipartite Densest $(k_{1},k_{2})$-Subgraph is deterministic,
then so is the algorithm for Densest $k$-Subgraph.

##### Dense $k$-Coloring.

The input to the Dense $k$-Coloring problem consists of an $n$-vertex graph
$G$ and an integer $k>0$, such that $n$ is an integral multiple of $k$. The
goal is to compute a partition of $V(G)$ into $n/k$ subsets
$S_{1},\ldots,S_{n/k}$ of cardinality $k$ each, while maximizing
$\sum_{i=1}^{n/k}|E_{G}(S_{i})|$. An instance of the Dense $k$-Coloring
problem is denoted by $\mathrm{DkC}(G,k)$, and the value of the optimal
solution to instance $\mathrm{DkC}(G,k)$ is denoted by
$\mathrm{OPT_{DkC}}(G,k)$.

#####  $(r,h)$-Graph Partitioning.

The input to the (r,h)-Graph Partitioning problem consists of a graph $G$, and
integers $r,h>0$. The goal is to compute $r$ vertex-disjoint subgraphs
$H_{1},\ldots,H_{r}$ of $G$, such that for all $1\leq i\leq r$,
$|E(H_{i})|\leq h$, while maximizing $\sum_{i=1}^{r}|E(H_{i})|$. An instance
of the (r,h)-Graph Partitioning problem is denoted by $\mathrm{GP}(G,r,h)$,
and the value of the optimal solution to instance $\mathrm{GP}(G,r,h)$ is
denoted by $\mathrm{OPT_{GP}}(G,r,h)$.

##### Maximum Bounded-Crossing Subgraph.

In the Maximum Bounded-Crossing Subgraph problem, the input is a graph $G$ and
an integer $L>0$. The goal is to compute a subgraph $H\subseteq G$ with
$\mathsf{CrN}(H)\leq L$, while maximizing $|E(H)|$. An instance of the Maximum
Bounded-Crossing Subgraph problem is denoted by $\mathrm{MBCS}(G,L)$, and the
value of the optimal solution to instance $\mathrm{MBCS}(G,L)$ is denoted by
$\mathrm{OPT_{MBCS}}(G,L)$. We note that we can assume that $L\leq|V(G)|^{4}$,
as otherwise the optimal solution is the whole graph $G$, since the crossing
number of a simple graph $G$ is at most $|E(G)|^{2}\leq|V(G)|^{4}$.

###  2.3 Chernoff Bound

We use the following standard version of Chernoff Bound (see. e.g., [DP09]).

######  Lemma 2.2 (Chernoff Bound).

Let $X_{1},\ldots,X_{n}$ be independent randon variables taking values in
$\\{0,1\\}$. Let $X=\sum_{1\leq i\leq n}X_{i}$, and let $\mu=\text{\bf
E}\left[X\right]$. Then for any $t>2e\mu$,

$\Pr\Big{[}X>t\Big{]}\leq 2^{-t}.$

Additionally, for any $0\leq\delta\leq 1$,

$\Pr\Big{[}X<(1-\delta)\cdot\mu\Big{]}\leq e^{-\frac{\delta^{2}\cdot\mu}{2}}.$

###  2.4 Auxiliary Lemma

We use the following simple lemma.

######  Lemma 2.3.

There is an efficient algorithm, that, given a graph $G$, a subset $S$ of its
vertices, and a parameter $\frac{2}{|S|}<\beta<1$, computes a set
$S^{\prime}\subseteq S$ of vertices, such that
$|S^{\prime}|\leq\beta\cdot|S|$, and
$|E_{G}(S^{\prime})|\geq\Omega(\beta^{2}\cdot|E_{G}(S)|)$ holds.

Proof: Consider the graph $G^{\prime}=G[S]$ and denote $|S|=k$. We iteratively
remove the lowest-degree vertex from $G^{\prime}$, until $G^{\prime}$ contains
$\left\lfloor\beta k\right\rfloor$ vertices. Once the algorithm terminates, we
output $S^{\prime}=V(G^{\prime})$. It now remains to show that
$|E_{G^{\prime}}(S^{\prime})|\geq\Omega(\beta^{2}|E(G^{\prime})|)$.

Observe that, if $H$ is an $n$-vertex graph, and $v$ is a lowest-degree vertex
of $H$, then the degree of $v$ in $H$ is at most $2|E(H)|/n$. Therefore, if
vertex $v$ is removed from $H$, then $|E(H)|$ decreases by at most a factor
$(1-2/n)$. Therefore,

$\frac{|E_{G^{\prime}}(S^{\prime})|}{|E(G^{\prime})|}\geq\bigg{(}1-\frac{2}{k}\bigg{)}\bigg{(}1-\frac{2}{k-1}\bigg{)}\cdots\bigg{(}1-\frac{2}{\left\lfloor\beta
k\right\rfloor+1}\bigg{)}=\frac{\left\lfloor\beta
k\right\rfloor\cdot(\left\lfloor\beta
k\right\rfloor-1)}{k\cdot(k-1)}=\Omega(\beta^{2}).$

##  3 Conditional Hardness of Densest $k$-Subgraph

###  3.1 Low-Degree CSP Conjecture

We consider the Bipartite 2-CSP problem, that is defined as follows. The input
to the problem consists of two sets $X,Y$ of variables, together with an
integer $A>1$. Every variable $z\in X\cup Y$ takes values in set
$[A]=\\{1,\ldots,A\\}$. We are also given a collection $\mathcal{C}$ of
constraints, where each constraint $C(x,y)\in\mathcal{C}$ is defined over a
pair of variables $x\in X$ and $y\in Y$. For each such constraint, we are
given a truth table that, for every pair of assignments $a$ to $x$ and
$a^{\prime}$ to $y$, specifies whether $(a,a^{\prime})$ _satisfy_ constraint
$C(x,y)$. The _value_ of the CSP is the largest fraction of constraints that
can be simultaneously satisfied by an assignment to the variables.

We associate with each constraint $C=C(x,y)\in\mathcal{C}$, a bipartite graph
$G_{C}=(L,R,E)$, where $L=R=[A]$, and there is an edge $(a,a^{\prime})$ in $E$
iff the assignments $a$ to $x$ and $a^{\prime}$ to $y$ satisfy $C$. Notice
that instance ${\mathcal{I}}$ of the Bipartite 2-CSP problem is completely
defined by $X,Y,A,\mathcal{C}$, and the graphs in
$\\{G_{C}\\}_{C\in\mathcal{C}}$, so we will denote
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$. The _size_
of instance ${\mathcal{I}}$ is defined to be
$\operatorname{size}({\mathcal{I}})=|\mathcal{C}|\cdot A^{2}+|X|+|Y|$.

Consider some instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP. We say that ${\mathcal{I}}$ is a _$d$ -to-$d$ instance_ if, for every
constraint $C$, every vertex of graph $G_{C}=(L,R,E)$ has degree at most $d$.

Consider now some functions
$d(n),s(n):\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$. We assume that, for all
$n$, $d(n)\geq 1$ and $s(n)<1$. In a $(d(n),s(n))$-LD-2CSP problem, the input
is an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP, such that, if we denote by $n=\operatorname{size}({\mathcal{I}})$, then
the instance is $d(n)$-to-$d(n)$. We say that ${\mathcal{I}}$ is a Yes-
Instance, if there is some assignment to the variables of $X\cup Y$ that
satisfies at least $|\mathcal{C}|/2$ of the constraints, and we say that it is
a No-Instance, if the largest number of constraints of $\mathcal{C}$ that can
be simultaneously satisfied by any assignment is at most
$s(n)\cdot|\mathcal{C}|$. Given an instance ${\mathcal{I}}$ of
$(d(n),s(n))$-LD-2CSP problem, the goal is to distinguish between the case
where ${\mathcal{I}}$ is a Yes-Instance and the case where ${\mathcal{I}}$ is
a No-Instance. If ${\mathcal{I}}$ is neither a Yes-Instance nor a No-Instance,
the output of the algorithm can be arbitrary. We now state our conjecture
regarding hardness of $(d(n),s(n))$-LD-2CSP, that is a restatement of 1 from
the Introduction.

######  Conjecture 2 (Low-Degree CSP Conjecture).

There is a constant $0<\varepsilon\leq 1/2$, such that the
$(d(n),s(n))$-LD-2CSP problem is NP-hard for $d(n)=2^{(\log n)^{\varepsilon}}$
and $s(n)=1/2^{64(\log n)^{1/2+\varepsilon}}$.

###  3.2 Conditional Hardness of Densest $k$-Subgraph

In the remainder of this section, we prove the following theorem on the
conditional hardness of Densest $k$-Subgraph.

######  Theorem 3.1.

Assume that 2 holds and that $\mbox{\sf P}\neq\mbox{\sf NP}$. Then for some
$0<\varepsilon\leq 1/2$, there is no efficient approximation algorithm for
Densest $k$-Subgraph problem that achieves approximation factor $2^{(\log
N)^{\varepsilon}}$, where $N$ is the number of vertices in the input graph.

In fact we will prove a slightly more general theorem, that will be useful for
us later.

######  Theorem 3.2.

Suppose there is an algorithm for the Densest $k$-Subgraph problem, that,
given an instance $\mathrm{DkS}(G,k)$ with $|V(G)|=N$, in time at most $T(N)$,
computes a factor $2^{(\log N)^{\varepsilon}}$-approximate solution to the
problem, for some constant $0<\varepsilon\leq 1/2$. Then there is an
algorithm, that, given an instance ${\mathcal{I}}$ of $(d(n),s(n))$-LD-2CSP
problem of size $n$, where $d(n)=2^{(\log n)^{\varepsilon}}$ and
$s(n)=1/2^{64(\log n)^{1/2+\varepsilon}}$, responds “YES” or ”NO”, in time
$O(\textnormal{poly}(n)\cdot T(\textnormal{poly}(n)))$. If ${\mathcal{I}}$ is
a Yes-Instance, the algorithm is guaranteed to respond “YES”, and if it is a
No-Instance, it is guaranteed to respond “NO”.

Theorem 3.1 immediately follows from Theorem 3.2. The remainder of this
section is dedicated to proving Theorem 3.2. A central notion that we use is a
_constraint graph_ that is associated with an instance ${\mathcal{I}}$ of
$2$-CSP.

##### Constraint Graph.

Let ${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ be an
instance of the Bipartite 2-CSP problem. The _constraint graph_ associated
with instance ${\mathcal{I}}$ is denoted by $H({\mathcal{I}})$, and it is
defined as follows. The set of vertices of $H({\mathcal{I}})$ is the union of
two subsets: set $V=\\{v(x)\mid x\in X\\}$ of vertices representing the
variables of $X$, and set $U=\\{v(y)\mid y\in Y\\}$ of vertices representing
the variables of $Y$. For convenience, we will not distinguish between the
vertices of $V$ and the variables of $X$, so we will identify each variable
$x\in X$ with its corresponding vertex $v(x)$. Similarly, we will not
distinguish between vertices of $U$ and variables of $Y$. The set of edges of
$H({\mathcal{I}})$ contains, for every constraint $C=C(x,y)\in\mathcal{C}$,
edge $e_{C}=(x,y)$. We say that edge $e_{C}$ _represents_ the constraint $C$.
Notice that, if $E^{\prime}$ is a subset of edges of $H({\mathcal{I}})$, then
we can define a set $\Phi(E^{\prime})\subseteq\mathcal{C}$ of constraints that
the edges of $E^{\prime}$ represent, namely:
$\Phi(E^{\prime})=\\{C\in\mathcal{C}\mid e_{C}\in E^{\prime}\\}$. Next, we
define bad sets of constraints and bad collections of edges.

######  Definition 3.3 (Bad Set of Constraints and Bad Collection of Edges).

Let $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ be a collection of constraints
of an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP. We say that $\mathcal{C}^{\prime}$ is a _bad set of constraints_ if the
largest number of constraints of $\mathcal{C}^{\prime}$ that can be
simultaneously satisfied by any assignment to the variables of $X\cup Y$ is at
most $\frac{|\mathcal{C}^{\prime}|}{4}$. If $E^{\prime}\subseteq
E(H({\mathcal{I}}))$ is a set of edges of $H({\mathcal{I}})$, whose
corresponding set $\Phi(E^{\prime})$ of constraints is bad, then we say that
$E^{\prime}$ is a _bad collection of edges_.

The next observation easily follows from the definition of a bad set of
constraints.

######  Observation 3.4.

Let ${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ be an
instance of bipartite 2-CSP, and let
$\mathcal{C}^{\prime},\mathcal{C}^{\prime\prime}\subseteq\mathcal{C}$ be two
disjoint sets of constraints that are both bad. Then
$\mathcal{C}^{\prime}\cup\mathcal{C}^{\prime\prime}$ is also a bad set of
constraints.

Next, we define good subsets of constraints and good subgraphs of the
constraint graph $H({\mathcal{I}})$.

######  Definition 3.5 (Good Set of Constraints and Good Subgraphs of
$H({\mathcal{I}})$).

Let $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ be a collection of constraints
of an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP, and let $0<\beta\leq 1$ be a parameter. We say that
$\mathcal{C}^{\prime}$ is a _$\beta$ -good set of constraints_, if there is an
assigmnet to variables of $X\cup Y$ that satisfies at least
$\frac{|\mathcal{C}^{\prime}|}{\beta}$ constraints of $\mathcal{C}^{\prime}$.
If $E^{\prime}\subseteq E(H({\mathcal{I}}))$ is a set of edges of
$H({\mathcal{I}})$, whose corresponding set $\Phi(E^{\prime})$ of constraints
is $\beta$-good, then we say that $E^{\prime}$ is a _$\beta$ -good collection
of edges_. Lastly, if $H^{\prime}\subseteq H({\mathcal{I}})$ is a subgraph of
the constraint graph, and the set $E(H^{\prime})$ of edges is $\beta$-good,
then we say that graph $H^{\prime}$ is _$\beta$ -good_.

The next observation easily follows from the definition of a good set of
constraints.

######  Observation 3.6.

Let ${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ be an
instance of bipartite 2-CSP, let $0<\beta\leq 1$ be a parameter, and let
$H^{\prime},H^{\prime\prime}$ be two subgraphs of $H({\mathcal{I}})$ that are
both $\beta$-good and disjoint in their vertices. Then graph $H^{\prime}\cup
H^{\prime\prime}$ is also $\beta$-good.

The observation follows from the fact that, since graphs
$H^{\prime},H^{\prime\prime}$ are disjoint in their vertices, if we let
$\mathcal{C}^{\prime}=\Phi(E(H^{\prime}))$,
$\mathcal{C}^{\prime\prime}=\Phi(E(H^{\prime\prime}))$ be the sets of
constraints associated with the edge sets of both graphs, then the variables
participating in the constraints of $\mathcal{C}^{\prime}$ are disjoint from
the variables participating in the constraints of
$\mathcal{C}^{\prime\prime}$.

The following theorem is key in proving Theorem 3.2.

######  Theorem 3.7.

Assume that there exists a constant $0<\varepsilon\leq 1/2$, and an
$\alpha(N)$-approximation algorithm ${\mathcal{A}}$ for the Densest
$k$-Subgraph problem, whose running time is at most $T(N)$, where $N$ is the
number of vertices in the input graph, and $\alpha(N)=2^{(\log
N)^{\varepsilon}}$. Then there is an algorithm, whose input consists of an
instance ${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of
Bipartite 2-CSP and parameter $n$ that is greater than a large enough
constant, so that $\operatorname{size}({\mathcal{I}})\leq n$ holds, and
${\mathcal{I}}$ is a $d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, for
$d(n)\leq 2^{(\log n)^{\varepsilon}}$. Let $\beta=2^{8(\log
n)^{1/2+\varepsilon}}$, and let $r=\left\lceil\beta\cdot\log n\right\rceil$.
The algorithm returns a partition $(E^{b},E_{1},\ldots,E_{r})$ of
$E(H({\mathcal{I}}))$, such that $E^{b}$ is a bad set of edges, and for all
$1\leq i\leq r$, set $E_{i}$ of edges is $\beta^{3}$-good. The running time of
the algorithm is $O(T(\textnormal{poly}(n))\cdot\textnormal{poly}(n)$.

The proof of Theorem 3.2 easily follows from Theorem 3.7. Assume that there
exists a constant $0<\varepsilon\leq 1/2$, and an $\alpha(N)$-approximation
algorithm ${\mathcal{A}}$ for the Densest $k$-Subgraph problem, whose running
time is at most $T(N)$, where $N$ is the number of vertices in the input
graph, and $\alpha(N)=2^{(\log N)^{\varepsilon}}$. We show an algorithm for
the $(d(n),s(n))$-LD-2CSP problem, for $d(n)=2^{(\log n)^{\varepsilon}}$ and
$s(n)=1/2^{64(\log n)^{1/2+\varepsilon}}$. Let
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ be an input
instance of the Bipartite 2-CSP problem, with
$\operatorname{size}({\mathcal{I}})=n$, so that ${\mathcal{I}}$ is a
$d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, for $d(n)\leq 2^{(\log
n)^{\varepsilon}}$. If $n$ is bounded by a constant, then we can determine
whether ${\mathcal{I}}$ is a Yes-Instance or a No-Instance by exhaustively
trying all assignments to its variables. Therefore, we assume that $n$ is
greater than a large enough constant. We apply the algorithm from Theorem 3.7
to this instance ${\mathcal{I}}$. Let $(E^{b},E_{1},\ldots,E_{r})$ be the
partition of the edges of $E(H({\mathcal{I}}))$ that the algorithm returns. We
now consider two cases.

Assume first that $|E^{b}|>2|\mathcal{C}|/3$. Let
$\mathcal{C}^{b}\subseteq\mathcal{C}$ be the set of all constraints that
correspond to the edges of $E^{b}$. Recall that set $\mathcal{C}^{b}$ of
constraints is bad, so in any assignment, at most
$\frac{|\mathcal{C}^{\prime}|}{4}$ of the constraints in $\mathcal{C}$ may be
satisfied. Therefore, if $f$ is any assignment to variables of $X\cup Y$, the
number of constraints in $\mathcal{C}$ that are not satisfied by $f$ is at
least $\frac{3|\mathcal{C}^{\prime}|}{4}>\frac{|\mathcal{C}|}{2}$. Clearly,
${\mathcal{I}}$ may not be a Yes-Instance in this case. Therefore, if
$|E^{b}|>2|\mathcal{C}|/3$, we report that ${\mathcal{I}}$ is a No-Instance.

If $|E^{b}|\leq 2|\mathcal{C}|/3$, then we report that ${\mathcal{I}}$ is a
Yes-Instance. It is now enough to show that, if $|E^{b}|\leq
2|\mathcal{C}|/3$, then instance ${\mathcal{I}}$ may not be a No-Instance. In
other words, it is enough to show that there is an assignment that satisfies
more than $\frac{|\mathcal{C}|}{2^{64(\log n)^{1/2+\varepsilon}}}$
constraints. Indeed, since $|E^{b}|\leq 2|\mathcal{C}|/3$, there is an index
$1\leq i\leq r$, with $|E_{i}|\geq\frac{|\mathcal{C}|}{3r}$. Since set $E_{i}$
of edges is $\beta^{3}$-good, there is an assignment to the variables of
$X\cup Y$, that satisfies at least
$\frac{|E_{i}|}{\beta^{3}}\geq\frac{|\mathcal{C}|}{3r\beta^{3}}$ constraints
that correspond to the edges of $E_{i}$. Recall that $\beta=2^{8(\log
n)^{1/2+\varepsilon}}$ and $r=\left\lceil\beta\cdot\log n\right\rceil$.
Therefore, $3r\beta^{3}\leq 6\beta^{4}\log n\leq 2^{64(\log
n)^{1/2+\varepsilon}}$. We conclude that there is an assignment satisfying at
least $|\mathcal{C}|/2^{64(\log n)^{1/2+\varepsilon}}$ constraints, and so
${\mathcal{I}}$ may not be a No-Instance. It is easy to verify that the
running time of the algorithm is
$O(T(\textnormal{poly}(n))\cdot\textnormal{poly}(n)$.

To conclude, we have shown that, if there is an $\alpha(N)$-approximation
algorithm ${\mathcal{A}}$ for the Densest $k$-Subgraph problem, with running
time at most $T(N)$, where $N$ is the number of vertices in the input graph,
and $\alpha(N)=2^{(\log N)^{\varepsilon}}$, then there is an algorithm for the
$(d(n),s(n))$-LD-2CSP problem, for $d(n)=2^{(\log n)^{\varepsilon}}$ and
$s(n)=1/2^{8(\log n)^{1/2+\varepsilon}}$, whose running time is
$O(T(\textnormal{poly}(n))\cdot\textnormal{poly}(n)$.

In the remainder of this section we prove Theorem 3.7.

###  3.3 Proof of Theorem 3.7

The following theorem is the main technical ingredient of the proof of Theorem
3.7.

######  Theorem 3.8.

Assume that there exists an $\alpha(N)$-approximation algorithm
${\mathcal{A}}$ for the Bipartite Densest $(k_{1},k_{2})$-Subgraph problem,
whose running time is at most $T(N)$, where $N$ is the number of vertices in
the input graph. Then there is an algorithm, that, given an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP and parameters $n,\beta\geq 1$, so that
$\operatorname{size}({\mathcal{I}})\leq n$, $\beta\geq
2^{30}(\alpha(n))^{3}(\log n)^{12}$, and ${\mathcal{I}}$ is a $d(n)$-to-$d(n)$
instance of Bipartite 2-CSP, for some function $d(n)$, in time
$O(T(n)\cdot\textnormal{poly}(n))$, does one of the following:

  * •

either correctly establishes that graph $H({\mathcal{I}})$ is
$\beta^{3}$-good; or

  * •

computes a bad set $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ of constraints,
with $|\mathcal{C}^{\prime}|\geq\frac{|\mathcal{C}|}{8\log^{2}n}$; or

  * •

computes a subgraph $H^{\prime}=(X^{\prime},Y^{\prime},E^{\prime})$ of
$H({\mathcal{I}})$, for which the following hold:

    * –

$|X^{\prime}|\leq\frac{2d(n)\cdot|X|}{\beta}$;

    * –

$|Y^{\prime}|\leq\frac{2d(n)\cdot|Y|}{\beta}$; and

    * –

$|E^{\prime}|\geq\frac{\operatorname{vol}_{H}(X^{\prime}\cup
Y^{\prime})}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$.

We prove Theorem 3.8 in Section Section 3.4, after we complete the proof of
Theorem 3.7 using it. We start with the following corollary of Theorem 3.8.

######  Corollary 3.9.

Assume that there exists an $\alpha(N)$-approximation algorithm
${\mathcal{A}}$ for the BDkS problem, whose running time is at most $T(N)$,
where $N$ is the number of vertices in the input graph. Then there is an
algorithm, whose input consists of an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP and parameters $n,\beta\geq 1$, so that
$\operatorname{size}({\mathcal{I}})\leq n$, $\beta\geq
2^{30}(\alpha(n))^{3}(\log n)^{12}$, and ${\mathcal{I}}$ is a $d(n)$-to-$d(n)$
instance of Bipartite 2-CSP. The algorithm returns a partition $(E_{1},E_{2})$
of $E(H({\mathcal{I}}))$, where $E_{1}$ is a bad set of edges, and:

  * •

either the algorithm correctly certifies that $E_{2}$ is a $\beta^{3}$-good
set of edges; or

  * •

it computes a subgraph $H^{\prime}=(X^{\prime},Y^{\prime},E^{\prime})$ of
$H({\mathcal{I}})$, with $E(H^{\prime})\subseteq E_{2}$, for which the
following hold:

    * –

$|X^{\prime}|\leq\frac{2d(n)\cdot|X|}{\beta}$;

    * –

$|Y^{\prime}|\leq\frac{2d(n)\cdot|Y|}{\beta}$; and

    * –

$|E^{\prime}|\geq\frac{|E^{*}_{2}|}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$,
where $E^{*}_{2}$ is a set of edges containing every edge $e\in E_{2}$ with
exactly one endpoint in $V(H^{\prime})$.

The running time of the algorithm is $O(T(n)\cdot\textnormal{poly}(n))$.

Proof: The algorithm is iterative. We start with $E_{1}=\emptyset$,
$E_{2}=E(H({\mathcal{I}}))$ and $H=H({\mathcal{I}})$. We then iterate. In
every iteration, we compute a graph $H^{\prime}=H\setminus E_{1}$. We denote
by $\mathcal{C}^{\prime}=\Phi(E(H^{\prime}))$ the set of all constraints of
$\mathcal{C}$ corresponding to the edges of $H^{\prime}$. Notice that graph
$H^{\prime}$ naturally defines a $d(n)$-to-$d(n)$ instance
${\mathcal{I}}^{\prime}$ of Bipartite 2-CSP, whose size is at most $n$, that
corresponds to the subset $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ of
constraints. We apply the algorithm from Theorem 3.8 to instance
${\mathcal{I}}^{\prime}$. If the outcome of the algorithm is a bad set
$\mathcal{C}^{\prime\prime}\subseteq\mathcal{C}^{\prime}$ of constraints, then
we let $\tilde{E}=\\{e_{C}\mid C\in\mathcal{C}^{\prime\prime}\\}$ be the set
of edges of $H^{\prime}$ corresponding to the constraints of
$\mathcal{C}^{\prime\prime}$. We add the edges of $\tilde{E}$ to $E_{1}$,
remove them from $E_{2}$, and continue to the next iteration.

If the algorithm from Theorem 3.8 certifies that graph $H^{\prime}$ is
$\beta^{3}$-good, then we terminate the algorithm with the current partition
$(E_{1},E_{2})$ of $E(H)$, and certify that the set $E_{2}$ of edges is
$\beta^{3}$-good.

Otherwise, the outcome of the algorithm from Theorem 3.8 must be a subgraph
$H^{\prime\prime}=(X^{\prime},Y^{\prime},E^{\prime})$ of $H^{\prime}$, with
$|X^{\prime}|\leq\frac{2d(n)\cdot|X|}{\beta}$ and
$|Y^{\prime}|\leq\frac{2d(n)\cdot|Y|}{\beta}$. The algorithm also guarantees
that $|E^{\prime}|\geq\frac{\operatorname{vol}_{H^{\prime}}(X^{\prime}\cup
Y^{\prime})}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$.

Let $E^{*}_{2}$ be the set of edges containing every edge $e\in E_{2}$ with
exactly one endpoint in $V(H^{\prime\prime})$. Since $E(H^{\prime})=E_{2}$, it
is immediate to verify that
$|E^{*}_{2}|\leq\operatorname{vol}_{H^{\prime}}(X^{\prime}\cup Y^{\prime})$.
Therefore, we are guaranteed that
$|E^{\prime}|\geq\frac{|E^{*}_{2}|}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$. We
return the current partition $(E_{1},E_{2})$ of $E(H)$ and subgraph
$H^{\prime\prime}$ of $H({\mathcal{I}})$, and terminate the algorithm.

It is easy to verify that the algorithm consists of at most
$O(\textnormal{poly}(n))$ iterations, and the running time of each iteration
is at most $O(T(n)\cdot\textnormal{poly}(n))$. Therefore, the total running
time of the algorithm is at most $O(T(n)\cdot\textnormal{poly}(n))$.

Next, we obtain the following corollary.

######  Corollary 3.10.

Assume that there exists a constant $0<\varepsilon\leq 1/2$, and an
$\alpha(N)$-approximation algorithm ${\mathcal{A}}$ for the Bipartite Densest
$(k_{1},k_{2})$-Subgraph problem, whose running time is at most $T(N)$, where
$N$ is the number of vertices in the input graph, and $\alpha(N)=2^{(4\log
N)^{\varepsilon}}$. Then there is an algorithm, whose input consists of an
instance ${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of
Bipartite 2-CSP and parameter $n$ that is greater than a large enough
constant, so that $\operatorname{size}({\mathcal{I}})\leq n$ holds, and
${\mathcal{I}}$ is a $d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, for
$d(n)\leq 2^{(\log n)^{\varepsilon}}$. Let $\beta=2^{8(\log
n)^{1/2+\varepsilon}}$. The algorithm returns a partition
$(E_{1},E_{2},E_{3})$ of $E(H({\mathcal{I}}))$, where $E_{1}$ is a bad set of
constraints, $E_{2}$ is a $\beta^{3}$-good set of constraints, and $|E_{1}\cup
E_{2}|\geq\frac{|E(H({\mathcal{I}}))|}{\beta}$. The running time of the
algorithm is $O(T(n)\cdot\textnormal{poly}(n))$.

Proof: Throughout the proof, we assume that there exists a constant
$0<\varepsilon\leq 1/2$, and an $\alpha(N)$-approximation algorithm
${\mathcal{A}}$ for the Bipartite Densest $(k_{1},k_{2})$-Subgraph problem,
whose running time is at most $T(N)$, where $N$ is the number of vertices in
the input graph, and $\alpha(N)=2^{(2\log N)^{\varepsilon}}$. Assume that we
are given an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP, together with a parameter $n$ that is greater than a large enough
constant, so that $\operatorname{size}({\mathcal{I}})\leq n$, and
${\mathcal{I}}$ is a $d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, for
$d(n)\leq 2^{(\log n)^{\varepsilon}}$. For convenience, we denote
$H=H({\mathcal{I}})$. Our algorithm uses a parameter
$\eta=2^{12}d(n)\cdot\alpha(n)\cdot\log^{4}n$.

The algorithm is iterative. Over the course of the algorithm, we maintain a
collection ${\mathcal{H}}$ of subgraphs of $H$, and another subgraph $H^{g}$
of $H$. We will ensure that, throughout the algorithm, all graphs in
${\mathcal{H}}\cup\\{H^{g}\\}$ are mutually disjoint in their vertices. We
denote by $E^{g}=E(H^{g})$ and
$E^{1}=\bigcup_{H^{\prime}\in{\mathcal{H}}}E(H^{\prime})$. Additionally, we
maintain another set $E^{b}$ of edges of $H$, that is disjoint from $E^{g}\cup
E^{1}$, and we denote by $E^{0}=E(H)\setminus(E^{g}\cup E^{b}\cup E^{1})$ the
set of all remaining edges of $H$. We ensure that the following invariants
hold throughout the algorithm.

  1. I1.

set $E^{g}=E(H^{g})$ of edges is $\beta^{3}$-good;

  2. I2.

set $E^{b}$ of edges is bad; and

  3. I3.

all graphs in ${\mathcal{H}}\cup\\{H^{g}\\}$ are disjoint in their vertices.

Intuitively, we will start with the set ${\mathcal{H}}$ containing a single
graph $H$, and $E^{g}=E^{b}=E^{0}=\emptyset$. As the algorithm progresses, we
will iteratively add edges to sets $E^{g},E^{b}$ and $E^{0}$, while
partitioning the graphs in ${\mathcal{H}}$ into smaller subgraphs. The
algorithm will terminate once ${\mathcal{H}}=\emptyset$. The key in the
analysis of the algorithm is to ensure that $|E^{0}|$ is relatively small when
the algorithm terminates. We do so via a charging scheme: we assign a budget
to every edge of $E^{1}\cup E^{g}\cup E^{b}$, that evolves over the course of
the algorithm, and we keep track of this budget over the course of the
algorithm.

In order to define vertex budgets, we will assign, to every graph
$H\in{\mathcal{H}}$ a _level_ , that is an integer between $0$ and
$\left\lceil\log n\right\rceil$. We will ensure that, throughout the
algorithm, the following additional invariants hold:

  1. I4.

If $H^{\prime}\in{\mathcal{H}}$ is a level-$i$ graph, then the budget of every
edge $e\in E(H^{\prime})$ is at most $\eta^{i}$; and

  2. I5.

Throughout the algorithm’s execution, the total budget of all edges in
$E^{g}\cup E^{b}\cup E^{1}$ is at least $|E(H)|$.

Intuitively, at the end of the algorithm, we will argue that the level of
every graph in ${\mathcal{H}}$ is not too large, and that the budget of every
edge in $E^{g}\cup E^{b}\cup E^{1}$ is not too large. Since the total budget
of all edges in $E^{g}\cup E^{b}\cup E^{1}$ is at least $|E(H)|$, it will then
follow that $|E^{g}\cup E^{b}\cup E^{1}|$ is sufficiently large. We now
proceed to describe the algorithm.

Our algorithm will repeatedly use the algorithm from Corollary 3.9, with the
same functions $\alpha(N),d(n)$, and parameter $\beta$. In order to be able to
use the corollary, we need to estalish that $\beta\geq
2^{30}(\alpha(n))^{3}(\log n)^{12}$. This is immediate to verify since
$\beta=2^{8(\log n)^{1/2+\varepsilon}}$, $\alpha(n)=2^{(4\log
n)^{\varepsilon}}$, and $n$ is large enough.

##### Initialization.

At the beginning of the algorithm, we set $E^{0}=E^{g}=E^{b}=\emptyset$, and
we let ${\mathcal{H}}$ contain a single graph $H$, which is assigned level
$0$. Note that $E^{1}=E(H)$ must hold. Every edge $e\in E(H)$ is assigned
budget $b(e)=1$. Clearly, the total budget of all edges of $E^{1}\cup
E^{g}\cup E^{b}$ is $B=\sum_{e\in E^{1}\cup E^{g}\cup E^{b}}b(e)=|E(H)|$.

The algorithm performs iterations, as long as ${\mathcal{H}}\neq\emptyset$. In
every iteration, we select an arbitrary graph $H^{\prime}\in{\mathcal{H}}$ to
process. We now describe a single iteration.

##### Iteration description.

We now describe an iteration where some graph $H^{\prime}\in{\mathcal{H}}$ is
processed. We assume that graph $H^{\prime}$ is assigned level $i$. Notice
that graph $H^{\prime}$ naturally defines an instance
${\mathcal{I}}^{\prime}=(X^{\prime},Y^{\prime},A,\mathcal{C}^{\prime},\\{G_{C}\\}_{C\in\mathcal{C}^{\prime}})$
of Bipartite 2-CSP, where $X^{\prime}=V(H^{\prime})\cap X$,
$Y^{\prime}=V(H^{\prime})\cap Y$, $\mathcal{C}^{\prime}=\\{C\in\mathcal{C}\mid
e_{C}\in E(H^{\prime})\\}$, and the graphs $G_{C}$ for constraints
$C\in\mathcal{C}^{\prime}$ remain the same as in instance ${\mathcal{I}}$.
Clearly,
$\operatorname{size}({\mathcal{I}}^{\prime})\leq\operatorname{size}({\mathcal{I}})\leq
n$, and $H({\mathcal{I}}^{\prime})=H^{\prime}$. Furthermore, instance
${\mathcal{I}}^{\prime}$ remains a $d(n)$-to-$d(n)$ instance. We apply the
algorithm from Corollary 3.9 to instance ${\mathcal{I}}^{\prime}$, with
parameters $n$ and $\beta$ remaining unchanged. Consider the partition
$(E_{1},E_{2})$ of $E(H^{\prime})$ that the algorithm returns. Recall that the
set $E_{1}$ of edges is bad. We add the edges of $E_{1}$ to set $E^{b}$. From
Invariant I2 and 3.4, set $E^{b}$ of edges continues to be bad. If the
algorithm from Corollary 3.9 certified that $E_{2}$ is a $\beta^{3}$-good set
of edges, then we update graph $H^{g}$ to be $H^{g}\cup(H^{\prime}\setminus
E_{1})$, and we add the edges of $E_{2}$ to set $E^{g}$. We then remove graph
$H^{\prime}$ from ${\mathcal{H}}$, and continue to the next iteration. Note
that, from 3.6 and Invariants I1 and I3, the set $E^{g}$ of edges continues to
be $\beta^{3}$-good. It is easy to verify that all remaining invariants also
continue to hold.

From now on we assume that the algorithm from Corollary 3.9 returned a
subgraph
$H^{\prime\prime}=(X^{\prime\prime},Y^{\prime\prime},E^{\prime\prime})$ of
$H^{\prime}$, with $E^{\prime\prime}\subseteq E_{2}$, such that
$|X^{\prime\prime}|\leq\frac{2d(n)\cdot|X^{\prime}|}{\beta}$ and
$|Y^{\prime\prime}|\leq\frac{2d(n)\cdot|Y^{\prime}|}{\beta}$. In particular,
$|V(H^{\prime\prime})|=|X^{\prime\prime}|+|Y^{\prime\prime}|\leq\frac{2d(n)}{\beta}\cdot(|X^{\prime}|+|Y^{\prime}|)\leq\frac{2d(n)}{\beta}\cdot|V(H^{\prime})|$.
Additinally, if we denote by $E^{*}_{2}$ the subset of edges of $E_{2}$
containing all edges with exactly one endpoint in $X^{\prime\prime}\cup
Y^{\prime\prime}$, then
$|E^{\prime\prime}|\geq\frac{|E^{*}_{2}|}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$
must hold. We let $H^{*}$ be the graph obtained from $H^{\prime}\setminus
E_{1}$, by deleting the vertices of $H^{\prime\prime}$ from it, so
$V(H^{*})\cup V(H^{\prime\prime})=V(H^{\prime})$, and $E(H^{*})\cup
E(H^{\prime\prime})\cup E^{*}_{2}=E_{2}$. We remove graph $H^{\prime}$ from
${\mathcal{H}}$, and we add graphs $H^{\prime\prime}$ and $H^{*}$ to
${\mathcal{H}}$, with graph $H^{\prime\prime}$ assigned level $(i+1)$, and
graph $H^{*}$ assigned level $i$. We also add the edges of $E_{2}^{*}$ to
$E^{0}$, and we update the set $E^{1}$ of edges to contain all edges of
$\bigcup_{\tilde{H}\in{\mathcal{H}}}E(\tilde{H})$. Since we did not modify
graph $H^{g}$ in the current iteration, it is immediate to verify that
Invariants I1–I3 continue to hold. Next, we update the budgets of edges, in
order to ensure that Invariants I4 and I5 continue to hold. Intuitively, the
edges of $E^{*}_{2}$ are now added to set $E^{0}$, so we need to distribute
their budget among the edges of $E(H^{\prime\prime})$, in order to ensure that
the total budget of all edges in $E^{g}\cup E^{b}\cup E^{1}$ does not
decrease. This will ensure that Invariant I5 continues to hold. At the same
time, since the level of graph $H^{\prime\prime}$ is $(i+1)$, while the level
of graph $H^{\prime}$ was $i$, we can increase the budgets of the edges of
$E(H^{\prime})$ and still maintain Invariant I4.

Formally, recall that Corollary 3.9 guarantees that
$|E^{*}_{2}|\leq|E^{\prime\prime}|\cdot(2048d(n)\cdot\alpha(n)\cdot\log^{4}n)=\frac{|E^{\prime\prime}|\cdot\eta}{2}$.
From Invariant I4, the current budget of every edge in $E^{\prime\prime}\cup
E^{*}_{2}$ is bounded by $\eta^{i}$. Therefore, at the beginning of the
current iteration:

$\sum_{e\in E^{\prime\prime}\cup
E^{*}_{2}}b(e)\leq\eta^{i}\cdot\left(|E^{*}_{2}|+|E^{\prime\prime}|\right)\leq\eta^{i}\cdot|E^{\prime\prime}|\cdot\left(1+\frac{\eta}{2}\right)<\eta^{i+1}\cdot|E^{\prime\prime}|.$

We set the budget of every edge in $E^{\prime\prime}$ to be $\eta^{i+1}$, and
leave the budgets of all other edges unchanged. It is easy to verify that
$\bigcup_{e\in E^{g}\cup E^{b}\cup E^{1}}b(e)$ does not decrease in the
current iteration, so Invariant I5 continues to hold. It is also easy to
verify that Invariant I4 continues to hold. Therefore, all invariants continue
to hold at the end of the iteration. This completes the description of an
iteration.

The algorithm terminates when ${\mathcal{H}}=\emptyset$. Clearly, we obtain a
partition $(E^{g},E^{b},E^{0})$ of $E(H)$ into disjoint subsets, where the set
$E^{b}$ of edges is bad, and the set $E^{g}$ of edges is $\beta^{3}$-good. It
remains to show that $|E^{g}\cup E^{b}|\geq\frac{|E(H)|}{\beta}$. We use the
edge budgets in order to prove this. Let $L^{*}$ be the largest level of any
subgraph of $H$ that belonged to ${\mathcal{H}}$ at any time during the
algorithm. We start with the following key observation.

######  Observation 3.11.

$L^{*}\leq(\log n)^{1/2-\varepsilon}$.

Proof: Consider any graph $H^{\prime\prime}$ that was added to set
${\mathcal{H}}$ at any time during the algorithm’s execution, and assume that
$H^{\prime\prime}$ was assigned level $i$. Consider the iteration during which
$H^{\prime\prime}$ was added to ${\mathcal{H}}$, and let
$H^{\prime}\in{\mathcal{H}}$ be the graph that was processed during that
iteration. We refer to graph $H^{\prime}$ as the _parent-graph_ of
$H^{\prime\prime}$. Note that the level of $H^{\prime}$ is either $i$ or
$(i-1)$. Assume that it is the latter. Then, from the algorithm’s description,
$|V(H^{\prime\prime})|\leq\frac{2d(n)}{\beta}\cdot|V(H^{\prime})|$ must hold.

We can now construct a _partitioning tree_ , that contains a vertex
$v(H^{\prime})$ for every graph $H^{\prime}$ that was ever present in
${\mathcal{H}}$ over the course of the algorithm, an an edge between vertices
$v(H^{\prime})$ and $v(H^{\prime\prime})$ whenever graph $H^{\prime}$ is a
parent-graph of graph $H^{\prime\prime}$. The root of the tree is $v(H)$.
Consider now again some graph $H^{\prime\prime}$, and the unique path $P$ in
the partitioning tree, connecting $v(H)$ to $v(H^{\prime\prime})$. Denote the
vertices on this path by
$v(H)=v(H_{0}),v(H_{1}),\ldots,v(H_{r})=v(H^{\prime\prime})$, and assume that
these vertices appear on path $P$ in this order. For all $1\leq i\leq r$,
denote the level of graph $H_{i}$ by $L_{i}$. Then $0=L_{1}\leq
L_{2}\leq\cdots\leq L_{r}$ must hold. Moreover, for every index $0<i\leq r$,
either $L_{i}=L_{i-1}$; or $L_{i}=L_{i-1}+1$ hold. In the latter case,
$|V(H_{i})|\leq|V(H_{i-1})|\cdot\frac{2d(n)}{\beta}$. Denote
$\Delta=\frac{\log n}{\log\left(\frac{\beta}{2d(n)}\right)}$. We claim that
$L_{r}\leq\Delta$. Indeed, assume for contradiction that $L_{r}>\Delta$. Then
there is a collection $J\subseteq\\{1,\ldots,r\\}$ of at least $\Delta+1$
indices $i$, for which $L_{i}=L_{i-1}+1$. But then:

$|V(H^{\prime\prime})|\leq
n\cdot\left(\frac{2d(n)}{\beta}\right)^{\Delta+1}<1,$

a contradiction. We conclude that $L^{*}\leq\frac{\log
n}{\log\left(\frac{\beta}{2d(n)}\right)}$. Substituting $\beta=2^{8(\log
n)^{1/2+\varepsilon}}$ and $d(n)\leq 2^{(\log n)^{\varepsilon}}$, we get that:

$L^{*}\leq\frac{\log n}{\log\left(2^{6(\log
n)^{1/2+\varepsilon}}\right)}\leq(\log n)^{1/2-\varepsilon}.$

From Invariant I4, throughout the algorithm, for every edge $e\in E^{1}$,
$b(e)\leq\eta^{L^{*}}$ must hold. Once an edge is added to $E^{b}\cup E^{g}$,
its budget does not change. Therefore, at the end of the algorithm, the budget
of every edge in $E^{g}\cup E^{b}$ is at most $\eta^{L^{*}}$. On the other
hand, from Invariant I5, at the end of the algorithm, the total budget of all
edges in $E^{1}\cup E^{g}\cup E^{b}$ is at least $|E(H)|$. Therefore, at the
end of the algorithm:

$|E^{g}\cup E^{b}|\geq\frac{|E(H)|}{\eta^{L^{*}}}.$

We now bound $\eta^{L^{*}}$. Recall that
$\eta=2^{12}d(n)\cdot\alpha(n)\cdot\log^{4}n\leq 2^{4(\log n)^{\varepsilon}}$,
since $d(n)\leq 2^{(\log n)^{\varepsilon}}$, $\alpha(n)=2^{(4\log
n)^{\varepsilon}}$, and $n$ is large enough. Since, from 3.11, $L^{*}\leq(\log
n)^{1/2-\varepsilon}$, we get that $\eta^{L^{*}}\leq 2^{4(\log
n)^{1/2}}<\beta$, since $\beta=2^{8(\log n)^{1/2+\varepsilon}}$. Therefore,
$|E^{g}\cup E^{b}|\geq|E(H)|/\beta$ as required.

Lastly, it is easy to verify that the algorithm has at most
$\textnormal{poly}(n)$ iterations, and the running time of each iteration is
bounded by $O(T(n)\cdot\textnormal{poly}(n))$, so the total running time of
the algorithm is at most $O(T(n)\cdot\textnormal{poly}(n))$.

We are now ready to complete the proof of Theorem 3.7. Assume that there
exists a constant $0<\varepsilon\leq 1/2$, and an $\alpha(N)$-approximation
algorithm ${\mathcal{A}}$ for the Densest $k$-Subgraph problem, whose running
time is at most $T(N)$, where $N$ is the number of vertices in the input
graph, and $\alpha(N)=2^{(\log N)^{\varepsilon}}$. From Lemma 2.1, there
exists an $\alpha^{\prime}(N)$-approximation algorithm ${\mathcal{A}}$ for the
Bipartite Densest $(k_{1},k_{2})$-Subgraph problem, where $N$ is the number of
vertices in the input graph, and $\alpha^{\prime}(N)\leq O(\alpha(N^{2}))\leq
O\left(2^{(2\log N)^{\varepsilon}}\right)$. The running time of the algorithm
is at most $O(T(N^{2})\cdot\textnormal{poly}(N))$. Denote
$T^{\prime}(N)=O(T(N^{2})\cdot\textnormal{poly}(N))$ this bound on the running
time of the algorithm, and let $\alpha^{\prime\prime}(N)=2^{(4\log
N)^{\varepsilon}}$. Then there is an $\alpha^{\prime\prime}(N)$-approximation
algorithm for Bipartite Densest $(k_{1},k_{2})$-Subgraph with running time at
most $O(T^{\prime}(N))$. Indeed, if $N$ is greater than a sufficiently large
constant, then we can use Algorithm ${\mathcal{A}}$, to obtain a solution
whose approximation factor is $\alpha^{\prime}(N)\leq O\left(2^{(2\log
N)^{\varepsilon}}\right)\leq 2^{(4\log
N)^{\varepsilon}}\leq\alpha^{\prime\prime}(N)$. Otherwise, we can solve the
problem exactly via exhaustive search.

Assume now that we are given an instance
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ of Bipartite
2-CSP and parameter $n$ that is greater than a large enough constant, so that
$\operatorname{size}({\mathcal{I}})\leq n$ holds, and ${\mathcal{I}}$ is a
$d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, for $d(n)\leq 2^{(\log
n)^{\varepsilon}}$. Let $\beta=2^{8(\log n)^{1/2+\varepsilon}}$, and let
$r=\left\lceil\beta\cdot\log n\right\rceil$. For convenience, we denote
$H=H({\mathcal{I}})$. Initially, we set $E^{b}=\emptyset$. Our algorithm
performs $r$ iterations, where for all $1\leq j\leq r$, in iteration $j$ we
construct the set $E_{j}\subseteq E(H)$ of edges, that is $\beta^{3}$-good,
and possibly adds some edges to set $E^{b}$. We ensure that, throughout the
algorithm, the set $E^{b}$ of edges is bad.

Initially, $E^{b}=\emptyset$. We now describe the $j$th iteration. We assume
that sets $E_{1},\ldots,E_{j-1}$ of edges of $H$ were already defined. We
construct graph $H_{j}$, that is obtained from graph $H$, by deleting the
edges of $E_{1}\cup\cdots\cup E_{j-1}\cup E^{b}$ from it. Notice that graph
$H_{j}$ naturally defines an instance
${\mathcal{I}}_{j}=(X,Y,A,\mathcal{C}_{j},\\{G_{C}\\}_{C\in\mathcal{C}_{j}})$
of Bipartite 2-CSP, with $H_{j}=H({\mathcal{I}}_{j})$, where
$\mathcal{C}_{j}=\\{C\in\mathcal{C}\mid e_{C}\in E(H_{j})\\}$. We apply the
algorithm from Corollary 3.10 to graph $H_{j}$, with parameters $n,\beta$, and
$d(n)$ remaining unchanged. Consider a partition $(E^{1},E^{2},E^{3})$ of
$E(H_{j})$ that the algorithm returns. We add the edges of $E^{1}$ to set
$E^{b}$. Since both sets of edges are bad, from 3.4, set $E^{b}$ of edges
continues to be bad. We also set $E_{j}=E^{2}$, which is guaranteed to be a
$\beta^{3}$-good set of edges from Corollary 3.10. Recall that Corollary 3.10
also guarantees that $|E^{1}\cup E^{2}|\geq|E(H_{j})|/\beta$. We then continue
to the next iteration.

Since, from the above discussion, for all $1\leq j<r$,
$|E(H_{j+1})|\leq\left(1-\frac{1}{\beta}\right)|E(H_{j})|$, and since
$r=\left\lceil\beta\cdot\log n\right\rceil$, at the end of the algorithm, we
are guaranteed that the final collection $E^{b},E_{1},\ldots,E_{r}$ of subsets
of edges indeed partitions $E(H)$.

Notice that the running time of a single iteration is bounded by
$O(T^{\prime}(n)\cdot\textnormal{poly}(n))\leq
O(T(\textnormal{poly}(n))\cdot\textnormal{poly}(n))$. Since the number of
iterations is bounded by $\textnormal{poly}(n)$, the total running time of the
algorithm is bounded by $O(T(\textnormal{poly}(n))\cdot\textnormal{poly}(n))$.

In order to complete the proof of Theorem 3.7, it is now enough to prove
Theorem 3.8, which we do next.

###  3.4 Proof of Theorem 3.8

The proof partially relies on ideas and techniques from [CKN21]. Assume that
there exists an $\alpha(N)$-approximation algorithm ${\mathcal{A}}$ for the
Bipartite Densest $(k_{1},k_{2})$-Subgraph problem, whose running time is at
most $T(N)$, where $N$ is the number of vertices in the input graph. Let
${\mathcal{I}}=(X,Y,A,\mathcal{C},\\{G_{C}\\}_{C\in\mathcal{C}})$ be the input
instance of Bipartite 2-CSP, with $\operatorname{size}({\mathcal{I}})\leq n$.
For convenience, we denote $H=H({\mathcal{I}})$. If $|E(H)|\leq\beta^{3}$,
then graph $H$ is $\beta^{3}$-good, since we can compute an assignment to the
variables of $X\cup Y$ that satisfies at least one constraint of
$\mathcal{C}$. Therefore, we assume from now on that $|E(H)|>\beta^{3}$. We
can also assume that graph $H$ contains no isolated vertices, as isolated
vertices of $H$ correspond to variables that do not participate in any
constraints, and can be discarded.

The proof consists of four steps. In the first step, in order to simplify the
proof, we will regularize graph $H$, by computing a “nice” subgraph
$\tilde{H}\subseteq H$. In the second step, we will define an _assignment
graph_ associated with $\tilde{H}$, and we will use it in order to obtain an
instance of Bipartite Densest $(k_{1},k_{2})$-Subgraph, to which algorithm
${\mathcal{A}}$ will then be applied. In the last two steps, we will use the
outcome of algorithm ${\mathcal{A}}$ in order to either correctly establish
that graph $H$ is $\beta^{3}$-good, or to compute a bad subset of constraints,
or a subgraph $H^{\prime}$ of $H$ as required. We now describe each of the
three steps in turn.

####  3.4.1 Step 1: Regularization

In this step we will compute a subgraph $\tilde{H}$ of $H$ that has a
convenient structure. We refer to graphs with such structure as _nice
subgraphs_ of $H$, and define them next.

######  Definition 3.12 (Nice Subgraph of $H$).

Let $\tilde{H}=(\tilde{X},\tilde{Y},\tilde{E})$ be a subgraph of $H$, and let
$d_{1},d_{2}\geq 1$ be parameters. We say that $\tilde{H}$ is a
$(d_{1},d_{2})$-nice subgraph of $H$, if the following hold:

  * •

For every vertex $x\in\tilde{X}$, $d_{1}\leq\deg_{H}(x)<2d_{1}$;

  * •

For every vertex $y\in\tilde{Y}$, $d_{2}\leq\deg_{H}(y)<8d_{2}\log n$ and
$d_{2}\leq\deg_{\tilde{H}}(y)<2d_{2}$; and

  * •

$|\tilde{E}|\geq\frac{d_{1}}{4\log n}\cdot|\tilde{X}|$.

We say that $\tilde{H}$ is a _nice_ subgraph of $H^{\prime}$ if it is a
$(d_{1},d_{2})$-nice subgraph of $H$ for any pair $d_{1},d_{2}\geq 1$ of
parameters.

The first step of our algorithm is summarized in the following claim, that
allows us to compute a nice subgraph $\tilde{H}$ of $H$ that contains many
edges of $H$.

######  Claim 3.13.

There is an algorithm with running time $O(\textnormal{poly}(n))$, that
computes parameters $d_{1},d_{2}>1$, and a subgraph $\tilde{H}$ of $H$, such
that $\tilde{H}$ is a $(d_{1},d_{2})$-nice subgraph of $H$, and
$|E(\tilde{H})|\geq\frac{|E(H)|}{8\log^{2}n}$.

Proof: The proof uses standard regularization techniques, and consists of
three steps. Denote $H=(X,Y,E)$.

In the first step, we partition the vertices of $X$ into groups
$S_{0},\ldots,S_{q}$, for $q=\left\lceil\log n\right\rceil$, where for all
$0\leq i\leq q$, $S_{i}=\\{x\in X\mid 2^{i}\leq\deg_{H}(x)<2^{i+1}\\}$. We
also partition the set $E$ of edges into subsets $E_{0},\ldots,E_{q}$, where
for all $0\leq i\leq q$, set $E_{i}$ contains all edges $e\in E$ that are
incident to vertices of $S_{i}$. Clearly, there is an index $0\leq i^{*}\leq
q$, with $|E_{i^{*}}|\geq\frac{|E(H)|}{2\log n}$. We let
$\tilde{X}=S_{i^{*}}$, and we let $H_{1}$ be the graph whose vertex set is
$\tilde{X}\cup Y$, and edge set is $E_{i^{*}}$. We also define
$d_{1}=2^{i^{*}}$. Clearly, for every vertex $x\in\tilde{X}$,
$d_{1}\leq\deg_{H}(x)<2d_{1}$. This completes the first regularization step.

We now proceed to describe our second step, in which we consider the vertices
of $y\in Y$ one by one. We say that a vertex $y\in Y$ is _bad_ , if
$\deg_{H_{1}}(y)<\frac{\deg_{H}(y)}{4\log n}$. Let $Y^{\prime\prime}\subseteq
Y$ be the set of all bad vertices, and let $Y^{\prime}=Y\setminus
Y^{\prime\prime}$ be the set of all remaining vertices of $Y$, that we refer
to as _good vertices_. We use the following observation.

######  Observation 3.14.

$\sum_{y\in Y^{\prime\prime}}\deg_{H_{1}}(y)\leq\frac{|E(H_{1})|}{2}$.

Proof: Since, for every bad vertex $y$,
$\deg_{H_{1}}(y)<\frac{\deg_{H}(y)}{4\log n}$, we get that:

$\sum_{y\in Y^{\prime\prime}}\deg_{H_{1}}(y)<\sum_{y\in
Y^{\prime\prime}}\frac{\deg_{H}(y)}{4\log n}\leq\frac{|E(H)|}{4\log n}.$

Since, as observed above, $|E(H_{1})|\geq\frac{|E(H)|}{2\log n}$, the
observation follows.

We let $H_{2}$ be a graph that is obtained from $H_{1}$, by discarding the
vertices of $Y^{\prime\prime}$ from it. Therefore, $V(H_{2})=\tilde{X}\cup
Y^{\prime}$. Additionally, from 3.14,
$|E(H_{2})|\geq\frac{|E(H_{1})|}{2}\geq\frac{|E(H)|}{4\log n}$.

Lastly, in our third step, we perform a geometric grouping of the vertices of
$Y^{\prime}$ by their degree in $H_{2}$. Specifically, we let
$r=\left\lceil\log n\right\rceil$, and we partition the vertices of
$Y^{\prime}$ into sets $S^{\prime}_{0},\ldots,S^{\prime}_{r}$, where for
$0\leq j\leq r$, $S^{\prime}_{j}=\\{y\in Y^{\prime}\mid
2^{j}\leq\deg_{H_{2}}(y)<2^{j+1}\\}$. As before, we also partition the set
$E(H_{2})$ of edges into subsets $E^{\prime}_{0},\ldots,E^{\prime}_{r}$, where
for $0\leq j\leq r$ set $E^{\prime}_{j}$ contains all edges $e\in E(H_{2})$
that are incident to the vertices of $S^{\prime}_{j}$. As before, there must
be an index $0\leq j^{*}\leq r$ with
$|E^{\prime}_{j^{*}}|\geq\frac{|E(H_{2})|}{2\log
n}\geq\frac{|E(H)|}{8\log^{2}n}$. We set $\tilde{Y}=S^{\prime}_{j^{*}}$,
$d_{2}=2^{j^{*}}$, and we let $\tilde{H}$ be the graph whose vertex set is
$\tilde{X}\cup\tilde{Y}$, and edge set is $E^{\prime}_{j^{*}}$. We now verify
that this graph has all required properties.

First, as observed already, for every vertex $x\in\tilde{X}$,
$d_{1}\leq\deg_{H}(x)<2d_{1}$. Let $\tilde{E}=E(\tilde{H})$. As observed
already, $|\tilde{E}|\geq\frac{|E(H)|}{8\log^{2}n}$. Moreover, since, for
every vertex $x\in\tilde{X}$, $\deg_{H_{1}}(x)=\deg_{H}(x)\geq d_{1}$, we get
that $|E(H_{1})|\geq d_{1}\cdot|\tilde{X}|$, and so
$|\tilde{E}|\geq\frac{|E(H_{2})|}{2\log n}\geq\frac{|E(H_{1})|}{4\log
n}\geq\frac{d_{1}}{4\log n}\cdot|\tilde{X}|$.

Consider now some vertex $y\in\tilde{Y}$. From the definition of graph
$\tilde{H}$, it is immediate to verify that
$\deg_{\tilde{H}}(y)=\deg_{H_{2}}(y)$. Therefore,
$d_{2}\leq\deg_{\tilde{H}}(y)<2d_{2}$. Clearly,
$\deg_{H}(y)\geq\deg_{\tilde{H}}(y)\geq d_{2}$. Lastly, since vertex $y$ is
good, we get that:

$\deg_{\tilde{H}}(y)=\deg_{H_{2}}(y)=\deg_{H_{1}}(y)\geq\frac{\deg_{H}(y)}{4\log
n}.$

Since $\deg_{\tilde{H}}(y)<2d_{2}$, we get that $\deg_{H}(y)\leq(4\log
n)\deg_{\tilde{H}}(y)<8d_{2}\log n$. We conclude that
$d_{2}\leq\deg_{H}(y)<8d_{2}\log n$.

####  3.4.2 Step 2: Assignment Graph and Reduction to Bipartite Densest
$(k_{1},k_{2})$-Subgraph

Recall that we have computed, in the first step, a subgraph
$\tilde{H}=(\tilde{X},\tilde{Y},\tilde{E})$ of the graph $H=H({\mathcal{I}})$.
Since every edge of $H$ is associated with a distinct constraint in
$\mathcal{C}$, we can define a collection
$\tilde{\mathcal{C}}\subseteq\mathcal{C}$ of constraints corresponding to the
edges of $\tilde{H}$: $\tilde{\mathcal{C}}=\\{C\in\mathcal{C}\mid
e_{C}\in\tilde{E}\\}$.

Next, we define a bipartite graph $G=(U,V,\hat{E})$, called _assignment graph_
, that is associated with graph $\tilde{H}$. For every variable
$z\in\tilde{X}\cup\tilde{Y}$, we define a set $R(z)=\\{v(z,a)\mid 1\leq a\leq
A\\}$ of vertices that represent the possible assignments to variable $z$. We
then set $U=\bigcup_{x\in\tilde{X}}R(x)$, and $V=\bigcup_{y\in\tilde{Y}}R(y)$.
The set of vertices of $G$ is defined to be $U\cup V$.

In order to define the edges, consider any constraint
$C=C(x,y)\in\tilde{\mathcal{C}}$. We define a set $E(C)$ of at most $d(n)\cdot
A$ edges corresponding to $C$, as follows: we add an edge between vertex
$v(x,a)$ and vertex $v(y,a^{\prime})$ to $E(C)$ if assignments $a$ to $x$ and
$a^{\prime}$ to $y$ satisfy the constraint $C$. Since instance ${\mathcal{I}}$
is a $d(n)$-to-$d(n)$ instance of Bipartite 2-CSP, every vertex of $R(x)\cup
R(y)$ is incident to at most $d(n)$ edges of $E(C)$. We then let
$E(G)=\bigcup_{C\in\tilde{\mathcal{C}}}E(C)$.

Let $k_{1}=|\tilde{X}|$ and $k_{2}=|\tilde{Y}|$. We can then view graph $G$,
together with parameters $k_{1}$ and $k_{2}$ as an instance of the Bipartite
Densest $(k_{1},k_{2})$-Subgraph problem, $\mathrm{DkS}(G,k_{1},k_{2})$.
Notice that $|V(G)|\leq|\tilde{\mathcal{C}}|\cdot A^{2}\leq|\mathcal{C}|\cdot
A^{2}\leq\operatorname{size}({\mathcal{I}})\leq n$. We apply Algorithm
${\mathcal{A}}$ to instance $\mathrm{DkS}(G,k_{1},k_{2})$ of Bipartite Densest
$(k_{1},k_{2})$-Subgraph, and we let $S$ be the solution that the algorithm
returns. Denote $G^{\prime}=G[S]$, so the value of the solution is
$|E(G^{\prime})|$. Assume first that
$|E(G^{\prime})|<\frac{|\tilde{\mathcal{C}}|}{4\alpha(n)}$. We use the
following observation to show that, in this case, the set
$\tilde{\mathcal{C}}$ of constraints is bad.

######  Observation 3.15.

If the set $\tilde{\mathcal{C}}$ of constraints is not bad, then the value of
the optimal solution to instance $\mathrm{DkS}(G,k_{1},k_{2})$ of Bipartite
Densest $(k_{1},k_{2})$-Subgraph is at least
$\frac{|\tilde{\mathcal{C}}|}{4}$.

Proof: Assume that the set $\tilde{\mathcal{C}}$ of constraints is not bad.
Then there is an assignment $f$ to variables of $\tilde{X}\cup\tilde{Y}$ that
satisfies more than $\frac{|\tilde{\mathcal{C}}|}{4}$ constraints of
$\tilde{\mathcal{C}}$. For each variable $z\in\tilde{X}\cup\tilde{Y}$, we
denote the corresponding assignment by $f(z)$. Let $S^{\prime}$ be the set of
vertices of $G$ that contains, for every variable $x\in\tilde{X}$, vertex
$v(x,f(x))$, and for every variable $y\in\tilde{Y}$, vertex $v(y,f(y))$. Then
$S^{\prime}$ is a valid solution to instance $\mathrm{DkS}(G,k_{1},k_{2})$ of
Bipartite Densest $(k_{1},k_{2})$-Subgraph. Moreover, for every constraint
$C\in\tilde{\mathcal{C}}$ that is satisfied by the assignment $f$, an edge of
$E(C)$ must be contained in $G[S^{\prime}]$. Therefore, the value of solution
$S^{\prime}$ is at least $\frac{|\tilde{\mathcal{C}}|}{4}$.

From 3.15, if the set $\tilde{\mathcal{C}}$ of constraints is not bad, then
algorithm ${\mathcal{A}}$ must have returned a solution whose value is at
least $\frac{|\tilde{\mathcal{C}}|}{4\alpha(n)}$. Therefore, if the value of
the solution $S$ that the algorithm returns is less than
$\frac{|\tilde{\mathcal{C}}|}{4\cdot\alpha(n)}$, then we terminate the
algorithm, and return $\tilde{\mathcal{C}}$ as a bad set of constraints.
Recall that, from 3.13,
$|\tilde{\mathcal{C}}|=|E(\tilde{H})|\geq\frac{|E(H)|}{8\log^{2}n}=\frac{|\mathcal{C}|}{8\log^{2}n}$.
From now on we assume that the value of the soution $S$ is at least
$\frac{|\tilde{\mathcal{C}}|}{4\alpha(n)}$. We will use the set $S$ of
vertices of $G$, in order to either correctly certify that graph $H$ is
$\beta^{3}$-good, or to compute a subgraph $H^{\prime}\subseteq H$ with the
required properties. It will be convenient for us to further regularize graph
$G^{\prime}$, which we do in the next step.

####  3.4.3 Step 3: Further Regularization

It would be convenient for us to further regularize graph $G^{\prime}$, by
computing a subgraph $G^{\prime\prime}\subseteq G^{\prime}$, with
$|E(G^{\prime\prime})|$ roughly comparable to $|E(G^{\prime})|$, that has the
following additional properties. First, for all variables $x\in\tilde{X}$ with
$R(x)\cap V(G^{\prime\prime})\neq\emptyset$, the cardinalities of the sets
$R(x)\cap V(G^{\prime\prime})$ of vertices are roughly equal to each other (to
within factor $2$). Similarly, for all variables $y\in\tilde{Y}$ with
$R(y)\cap V(G^{\prime\prime})\neq\emptyset$, the cardinalities of the sets
$R(y)\cap V(G^{\prime\prime})$ of vertices are roughly equal to each other.
Lastly, for all constraints $C\in\tilde{\mathcal{C}}$ with $E(C)\cap
E(G^{\prime\prime})\neq\emptyset$, the cardinalities of the sets $E(C)\cap
E(G^{\prime\prime})$ of edges are roughly equal to each other. In this step,
we compute a subgraph $G^{\prime\prime}\subseteq G^{\prime}$ with all these
properties. The algorithm is summarized in the following claim.

######  Claim 3.16.

There is an algorithm with running time $O(\textnormal{poly}(n))$, that
computes a subgraph $G^{\prime\prime}\subseteq G^{\prime}$, subsets
$X^{*}\subseteq\tilde{X}$, $Y^{*}\subseteq\tilde{Y}$ of variables, a subset
$\mathcal{C}^{*}\subseteq\tilde{\mathcal{C}}$ of constraints, and integers
$q,q^{\prime},r\geq 1$, such that, if we denote, for every variable $z\in
X\cup Y$, $R^{\prime}(z)=R(z)\cap V(G^{\prime\prime})$, and for every
constraint $C\in\mathcal{C}$, $E^{\prime}(C)=E(C)\cap E(G^{\prime\prime})$,
then the following hold:

  * •

for every variable $x\in X^{*}$, $2^{q}\leq|R^{\prime}(x)|<2^{q+1}$, and for
$x\not\in X^{*}$, $R^{\prime}(x)=\emptyset$;

  * •

for every variable $y\in Y^{*}$,
$2^{q^{\prime}}\leq|R^{\prime}(y)|<2^{q^{\prime}+1}$, and for $y\not\in
Y^{*}$, $R^{\prime}(y)=\emptyset$;

  * •

for every constraint $C\in\mathcal{C}^{*}$,
$2^{r}\leq|E^{\prime}(C)|<2^{r+1}$, and for $C\not\in\mathcal{C}^{*}$,
$E^{\prime}(C)=\emptyset$; and

  * •

$|\mathcal{C}^{*}|\geq\frac{|\tilde{\mathcal{C}}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}$.

Proof: The proof follows a standard regularization process. Let
$E^{0}=E(G^{\prime})$, so that
$|E^{0}|\geq\frac{|\tilde{\mathcal{C}}|}{4\cdot\alpha(n)}$.

Our first step regularizes the variables of $\tilde{X}$. We group the
variables of $\tilde{X}$ into sets $J_{0},J_{1},\ldots,J_{\left\lceil\log
A\right\rceil}$. For all $0\leq i\leq\left\lceil\log A\right\rceil$, we let
$J_{i}=\\{x\in\tilde{X}\mid 2^{i}\leq|R(x)\cap V(G^{\prime})|<2^{i+1}\\}$.
Note that, if $R(x)\cap V(G^{\prime})=\emptyset$, then variable $x$ does not
belong to any of the groups that we have defined. We also partition the edges
of $E^{0}$ into groups $E_{0},E_{1},\ldots,E_{\left\lceil\log A\right\rceil}$,
where for all $0\leq i\leq\left\lceil\log A\right\rceil$, group $E_{i}$
contains all edges $e\in E^{0}$ that are incident to the vertices of
$\bigcup_{x\in J_{i}}(R(x)\cap V(G^{\prime}))$. It is easy to verify that
$(E_{0},\ldots,E_{\left\lceil\log A\right\rceil})$ is indeed a partition of
the set $E^{0}$ of edges. Therefore, there is an index $0\leq
q\leq\left\lceil\log A\right\rceil$ with $|E_{q}|\geq\frac{|E^{0}|}{2\log
A}\geq\frac{|E^{0}|}{2\log n}$. We then set $X^{*}=J_{q}$. For each such
variable $x\in X^{*}$, we set $R^{\prime}(x)=R(x)\cap V(G^{\prime})$, and for
each variable $x\in\tilde{X}\setminus X^{*}$, we set
$R^{\prime}(x)=\emptyset$. We also let $E^{1}=E_{q}$. From the above
discussion, $|E^{1}|\geq\frac{|E^{0}|}{2\log n}$, and, for every variable
$x\in X^{*}$, $2^{q}\leq|R^{\prime}(x)|<2^{q+1}$. Note that all edges of
$E^{1}$ are incident to vertices of $\bigcup_{x\in X^{*}}R^{\prime}(x)$.

Our second step is to regularize the variables of $\tilde{Y}$, exactly as
before. We group the variables of $\tilde{Y}$ into sets
$J^{\prime}_{0},J^{\prime}_{1},\ldots,J^{\prime}_{\left\lceil\log
A\right\rceil}$. For all $0\leq i^{\prime}\leq\left\lceil\log A\right\rceil$,
we let $J^{\prime}_{i^{\prime}}=\\{y\in\tilde{Y}\mid
2^{i^{\prime}}\leq|R(x)\cap V(G^{\prime})|<2^{i^{\prime}+1}\\}$. As before, if
$R(y)\cap V(G^{\prime})=\emptyset$, then variable $y$ does not belong to any
of the sets that we have defined. We also partition the edges of $E^{1}$ into
sets $E^{\prime}_{0},E^{\prime}_{1},\ldots,E^{\prime}_{\left\lceil\log
A\right\rceil}$, where for all $0\leq i^{\prime}\leq\left\lceil\log
A\right\rceil$, set $E_{i^{\prime}}$ contains all edges $e\in E^{1}$ that are
incident to the vertices of $\bigcup_{y\in J_{i^{\prime}}}(R(y)\cap
V(G^{\prime}))$. As before,
$(E^{\prime}_{0},\ldots,E^{\prime}_{\left\lceil\log A\right\rceil})$ is a
partition of the set $E^{1}$ of edges. Therefore, there is an index $0\leq
q^{\prime}\leq\left\lceil\log A\right\rceil$ with
$|E^{\prime}_{q^{\prime}}|\geq\frac{|E^{1}|}{2\log A}\geq\frac{|E^{1}|}{2\log
n}\geq\frac{|E^{0}|}{4\log^{2}n}$. We then set
$Y^{*}=J^{\prime}_{q^{\prime}}$. For each variable $y\in Y^{*}$, we let
$R^{\prime}(y)=R(y)\cap V(G^{\prime})$, and for each variable
$y\in\tilde{Y}\setminus Y^{*}$, we set $R^{\prime}(y)=\emptyset$. We also let
$E^{2}=E^{\prime}_{q^{\prime}}$. From the above discussion,
$|E^{2}|\geq\frac{|E^{0}|}{4\log^{2}n}$, and, for every variable $y\in Y^{*}$,
$2^{q^{\prime}}\leq|R^{\prime}(y)|<2^{y+1}$. Notice that every edge of $E^{2}$
is incident to a vertex of $\bigcup_{x\in X^{*}}R^{\prime}(x)$ and a vertex of
$\bigcup_{y\in Y^{*}}R^{\prime}(y)$.

Our third and final step is to regularize the constraints. Recall that for
each constraint $C=C(x,y)\in\tilde{\mathcal{C}}$, we defined a set $E(C)$ of
edges. Since $|R(x)|=A$ and $|R(y)|=A$, $|E(C)|\leq A^{2}\leq n$ must hold. We
group all constraints $C\in\tilde{\mathcal{C}}$ into sets
$\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{\left\lceil\log
n\right\rceil}$, where for all $0\leq j\leq\left\lceil\log n\right\rceil$, set
$\mathcal{C}_{j}$ contains all constraints $C\in\tilde{\mathcal{C}}$ with
$2^{j}\leq|E(C)\cap E^{2}|<2^{j+1}$. Note that, if $E(C)\cap E^{2}=\emptyset$,
then constraint $C$ does not belong to any set. Next, we define a partition
$E_{0}^{\prime\prime},E_{1}^{\prime\prime},\ldots,E_{\left\lceil\log
n\right\rceil}^{\prime\prime}$ of the set $E^{2}$ of edges: for $0\leq
j\leq\left\lceil\log n\right\rceil$, set $E^{\prime\prime}_{j}$ contains all
edges in $\bigcup_{C\in\mathcal{C}_{j}}(E(C)\cap E^{2})$. It is easy to verify
that $(E^{\prime\prime}_{0},\ldots,E_{\left\lceil\log
n\right\rceil}^{\prime\prime})$ is indeed a partition of $E^{2}$. Therefore,
there must be an index $0<r\leq\left\lceil\log n\right\rceil$, with
$|E^{\prime\prime}_{r}|\geq\frac{|E^{2}|}{2\log
n}\geq\frac{|E^{0}|}{8\log^{3}n}$. We let $\mathcal{C}^{*}=\mathcal{C}_{r}$
and $E^{3}=E^{\prime\prime}_{r}$. Since every constraint $C\in\mathcal{C}^{*}$
contributes at most $2^{r+1}$ edges to $E^{3}$, we get that:

$|\mathcal{C}^{*}|\geq\frac{|E^{3}|}{2^{r+1}}\geq\frac{|E^{0}|}{2^{r+4}\log^{3}n}\geq\frac{|\tilde{\mathcal{C}}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}.$

For every constraint $C\in\mathcal{C}^{*}$, we let $E^{\prime}(C)=E(C)\cap
E^{2}$, and for every constraint
$C\in\tilde{\mathcal{C}}\setminus\mathcal{C}^{*}$, we let
$E^{\prime}(C)=\emptyset$. We are now ready to define graph
$G^{\prime\prime}$. Its vertex set is $\left(\bigcup_{x\in
X^{*}}R^{\prime}(X)\right)\cup\left(\bigcup_{y\in Y^{*}}R^{\prime}(y)\right)$,
and its edge set is $\bigcup_{C\in\mathcal{C}^{*}}E^{\prime}(C)=E^{3}$. It is
immediate to verify, from the above discussion, that graph $G^{\prime}$, sets
$X^{*},Y^{*}$ of variables, and set $\mathcal{C}^{*}$ of constraints have all
required properties.

In the next observation, we establish some useful bounds on the cardinalities
of the sets $X^{*},Y^{*}$ of variables, and the set $\mathcal{C}^{*}$ of
constraints.

######  Observation 3.17.

All of the following bounds hold:

  * •

$|X^{*}|\leq\frac{|\tilde{X}|}{2^{q}}$;

  * •

$|Y^{*}|\leq\frac{|\tilde{Y}|}{2^{q^{\prime}}}$;

  * •

$|\mathcal{C}^{*}|\leq 2d_{1}|X^{*}|\leq\frac{2d_{1}|\tilde{X}|}{2^{q}}$; and

  * •

$|\mathcal{C}^{*}|\leq
2d_{2}|Y^{*}|\leq\frac{2d_{2}|\tilde{Y}|}{2^{q^{\prime}}}$.

Proof: From the definition of the instance $(G,k_{1},k_{2})$ of Bipartite
Densest $(k_{1},k_{2})$-Subgraph, graph $G^{\prime}$ contains at most
$k_{1}=|\tilde{X}|$ vertices of $\bigcup_{x\in\tilde{X}}R(x)$, and at most
$k_{2}=|\tilde{Y}|$ vertices of $\bigcup_{y\in\tilde{Y}}R(y)$. Since, for
every variable $x\in X^{*}$, $R^{\prime}(x)\subseteq V(G^{\prime})$ and
$|R^{\prime}(x)|\geq 2^{q}$, we get that
$|X^{*}|\leq\frac{|\tilde{X}|}{2^{q}}$. Similarly,
$|Y^{*}|\leq\frac{|\tilde{Y}|}{2^{q^{\prime}}}$.

Recall that, since $\tilde{H}$ is a nice subgraph of $H$, for every vertex
$x\in\tilde{H}$, $\deg_{\tilde{H}}(x)\leq\deg_{H}(x)\leq 2d_{1}$, and so $x$
may participate in at most $2d_{1}$ constraints of $\tilde{\mathcal{C}}$.
Since $\mathcal{C}^{*}\subseteq\tilde{\mathcal{C}}$ and
$X^{*}\subseteq\tilde{X}$, every variable $x\in X^{*}$ may participate in at
most $2d_{1}$ constraints of $\mathcal{C}^{*}$. Therefore,
$|\mathcal{C}^{*}|\leq 2d_{1}|X^{*}|$.

Similarly, since $\tilde{H}$ is a nice subgraph of $H$, for every vertex
$y\in\tilde{Y}$, $\deg_{\tilde{H}}(y)\leq 2d_{2}$. Using the same arguments as
before, $|\mathcal{C}^{*}|\leq 2d_{2}|Y^{*}|$.

Recall that, from 3.16,
$|\mathcal{C}^{*}|\geq\frac{|\tilde{\mathcal{C}}|}{2^{r+5}\cdot\alpha(n)\cdot\log^{3}n}$.
Since graph $\tilde{H}$ is a nice subgraph of $H$, we get that, for every
vertex $y\in\tilde{Y}$, $\deg_{\tilde{H}}(y)\geq d_{2}$. Therefore,
$|\tilde{\mathcal{C}}|\geq|\tilde{Y}|\cdot d_{2}$, and so:

$|\mathcal{C}^{*}|\geq\frac{d_{2}\cdot|\tilde{Y}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}.$
(1)

Similarly, from the definition of a nice subgraph,
$|\tilde{\mathcal{C}}|\geq\frac{d_{1}}{4\log n}\cdot|\tilde{X}|$, and so:

$|\mathcal{C}^{*}|\geq\frac{d_{1}\cdot|\tilde{X}|}{2^{r+8}\cdot\alpha(n)\cdot\log^{4}n}.$
(2)

Lastly, we show that both $2^{q},2^{q^{\prime}}$ are close to $2^{r}$, in the
following corollary of 3.17.

######  Corollary 3.18.

The following inequalities hold:

  * •

$\frac{2^{r}}{2d(n)}\leq 2^{q}\leq 2^{r+8}\cdot\alpha(n)\cdot\log^{4}n$; and

  * •

$\frac{2^{r}}{2d(n)}\leq 2^{q^{\prime}}\leq
2^{r+6}\cdot\alpha(n)\cdot\log^{3}n$.

Proof: Consider some constraint $C=C(x,y)\in\mathcal{C}^{*}$, and recall that
$|E^{\prime}(C)|\geq 2^{r}$. From the definition of the $d$-to-$d$ instances,
every vertex $v(x,a)\in R(x)$ may be incident to at most $d(n)$ edges of
$E(C)$. Since all edges of $E^{\prime}(C)$ are incident to vertices of
$R^{\prime}(x)$, and $|R^{\prime}(x)|\leq 2^{q+1}$, we get that
$|E^{\prime}(C)|\leq d(n)\cdot|R^{\prime}(x)|\leq d(n)\cdot 2^{q+1}$. We
conclude that $2^{r}\leq d(n)\cdot 2^{q+1}$.

Similarly, every vertex $v(y,a^{\prime})\in R(y)$ may be incident to at most
$d(n)$ edges of $E(C)$. Since all edges of $E^{\prime}(C)$ are incident to
vertices of $R^{\prime}(y)$, and $|R^{\prime}(y)|\leq 2^{q^{\prime}+1}$, we
get that $|E^{\prime}(C)|\leq d(n)\cdot 2^{q^{\prime}+1}$. This proves the
inequalities $\frac{2^{r}}{2d(n)}\leq 2^{q}$ and $\frac{2^{r}}{2d(n)}\leq
2^{q^{\prime}}$.

Next, we prove that $2^{q^{\prime}}\leq 2^{r+6}\cdot\alpha(n)\cdot\log^{3}n$.
Recall that, from Inequality 1,
$|\mathcal{C}^{*}|\geq\frac{d_{2}\cdot|\tilde{Y}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}$.
On the other hand, from the definition of a nice subgraph, every variable
$y\in Y^{*}$ may participate in at most $2d_{2}$ constraints of
$\mathcal{C}^{*}$, and, from 3.17,
$|Y^{*}|\leq\frac{|\tilde{Y}|}{2^{q^{\prime}}}$. Therefore:

$|\mathcal{C}^{*}|\leq
2d_{2}\cdot|Y^{*}|\leq\frac{2d_{2}|\tilde{Y}|}{2^{q^{\prime}}}.$ (3)

Combining the two inequalities, we get that: $2^{q^{\prime}}\leq
2^{r+6}\cdot\alpha(n)\cdot\log^{3}n$.

Lastly, we prove that $2^{q}\leq 2^{r+8}\cdot\alpha(n)\cdot\log^{4}n$. Recall
that, from Inequality 2,
$|\mathcal{C}^{*}|\geq\frac{d_{1}\cdot|\tilde{X}|}{2^{r+7}\cdot\alpha(n)\cdot\log^{4}n}$
holds. As before, from the definition of a nice subgraph, every variable $x\in
X^{*}$ may participate in at most $2d_{1}$ constraints of $\mathcal{C}^{*}$,
and, from 3.17, $|X^{*}|\leq\frac{|\tilde{X}|}{2^{q}}$. Therefore:

$|\mathcal{C}^{*}|\leq
2d_{1}\cdot|X^{*}|\leq\frac{2d_{1}\cdot|\tilde{X}|}{2^{q}}.$ (4)

Combining the two inequalities together, we get that: $2^{q}\leq
2^{r+8}\cdot\alpha(n)\cdot\log^{4}n$.

####  3.4.4 Step 4: Certifying that $H$ is a Good Graph or Computing a
Subgraph of $H$

We consider two cases, depending on whether $2^{r}\leq\beta$ holds. We start
by showing that, if $2^{r}\leq\beta$, then graph $H$ is $\beta^{3}$-good.

######  Observation 3.19.

If $2^{r}\leq\beta$, then graph $H$ is $\beta^{3}$-good.

Proof: We show that there exists an assignment to variables of $X\cup Y$ that
satisfies at least $|\mathcal{C}|/\beta^{3}$ constraints of $\mathcal{C}$. In
order to do it, we show a randomized algorithm that computes assignments to
variables of $X\cup Y$, such that the expected number of satisfied constraints
is at least $|\mathcal{C}|/\beta^{3}$.

The assignments are computed as follows. Consider a variable $x\in X$. If
$x\not\in X^{*}$, then we assign to $x$ an arbitrary value from $[A]$. Assume
now that $x\in X^{*}$. Recall that we have defined a set
$R^{\prime}(x)\subseteq R(x)$ of vertices, whose cardinality is at most
$2^{q+1}$. Set $R^{\prime}(x)$ of vertices naturally defines a collection
$\hat{A}(x)=\\{a\in[A]\mid v(x,a)\in R^{\prime}(x)\\}$ of assignments to
variable $x$, with $|\hat{A}(x)|\leq 2^{q+1}$. We choose an assignment
$a\in\hat{A}(x)$ uniformly at random, and assign value $a$ to $x$.

Assignments to variables of $Y$ are defined similarly. Consider a variable
$y\in Y$. If $y\not\in Y^{*}$, then we assign to $y$ an arbitrary value from
$[A]$. Assume now that $y\in Y^{*}$. Recall that we have defined a set
$R^{\prime}(y)\subseteq R(y)$ of vertices, whose cardinality is at most
$2^{q^{\prime}+1}$. Set $R^{\prime}(y)$ of vertices naturally defines a
collection $\hat{A}(y)=\\{a\in[A]\mid v(y,a)\in R^{\prime}(y)\\}$ of
assignments to variable $y$, with $|\hat{A}(y)|\leq 2^{q^{\prime}+1}$. We
choose an assignment $a^{\prime}\in\hat{A}(y)$ uniformly at random, and assign
value $a^{\prime}$ to $y$.

Recall that we have computed, in 3.16, a collection
$\mathcal{C}^{*}\subseteq\mathcal{C}$ of constraints, with
$|\mathcal{C}^{*}|\geq\frac{|\tilde{\mathcal{C}}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}$.
Consider now any constraint $C=C(x,y)\in\mathcal{C}^{*}$, and recall that
$x\in X^{*},y\in Y^{*}$ must hold. Recall that graph $G^{\prime\prime}$
contains a collection $E^{\prime}(C)\subseteq E(C)$ of edges, with
$|E^{\prime}(C)|\geq 2^{r}$. Consider now any such edge $e=(v(x,a),v(y,A))$.
We say that edge $e$ _wins_ if $x$ is assigned value $a$, and $y$ is assigned
value $a^{\prime}$. The probability that edge $e$ wins is at least
$\frac{1}{2^{q+1}\cdot 2^{q^{\prime}+1}}$. Notice that at most one edge of
$E^{\prime}(C)$ may win, and so the probability that any edge of
$E^{\prime}(C)$ wins is at least $\frac{|E^{\prime}(C)|}{2^{q+1}\cdot
2^{q^{\prime}+1}}\geq\frac{2^{r}}{2^{q+1}\cdot 2^{q^{\prime}+1}}$. If any edge
of $E^{\prime}(C)$ wins, the constraint $C$ is satisfied by the assignment
that the algorithm chooses. Therefore, the probability that a constraint
$C\in\mathcal{C}^{*}$ is satisfied is at least $\frac{2^{r}}{2^{q+1}\cdot
2^{q^{\prime}+1}}$.

Overall, the expected number of constraints that are satisfied by the
assignment is at least:

$\frac{|\mathcal{C}^{*}|\cdot 2^{r}}{2^{q+1}\cdot
2^{q^{\prime}+1}}\geq\frac{|\tilde{\mathcal{C}}|}{2^{8}\cdot\alpha(n)\cdot
2^{q}\cdot 2^{q^{\prime}}\cdot\log^{3}n}$

Recall that, from 3.13,
$|\tilde{\mathcal{C}}|=|E(\tilde{H})|\geq\frac{|E(H)|}{8\log^{2}n}=\frac{|\mathcal{C}|}{8\log^{2}n}$,
and, from Corollary 3.18, $2^{q}\cdot 2^{q^{\prime}}\leq
2^{2r+14}\cdot(\alpha(n))^{2}\cdot\log^{7}n\leq
2^{14}\cdot\beta^{2}\cdot(\alpha(n))^{2}\cdot\log^{7}n$, since we have assumed
that $2^{r}\leq\beta$. Therefore, the expected number of constraints of
$\mathcal{C}$ that are satisfied by the assignment is at least:

$\frac{|\tilde{\mathcal{C}}|}{2^{8}\cdot\alpha(n)\cdot 2^{q}\cdot
2^{q^{\prime}}\cdot\log^{3}n}\geq\frac{|\mathcal{C}|}{2^{11}\cdot\alpha(n)\cdot
2^{q}\cdot
2^{q^{\prime}}\cdot\log^{5}n}\geq\frac{|\mathcal{C}|}{2^{25}\cdot\beta^{2}\cdot(\alpha(n))^{3}\cdot\log^{12}n}\geq\frac{|\mathcal{C}|}{\beta^{3}},$

since $\beta\geq 2^{27}(\alpha(n))^{3}\log^{12}n$.

We conclude that there is an assignment to the variables of $X\cup Y$ that
satisfies at least $|\mathcal{C}|/\beta^{3}$ constraints of $\mathcal{C}$, and
so graph $H$ is $\beta^{3}$-good.

If $2^{r}\leq\beta$, then we terminate the algorithm and report that graph $H$
is $\beta$-good.

From now on we assume that $2^{r}>\beta$. In this case, we return a subgraph a
subgraph $H^{\prime}=(X^{\prime},Y^{\prime},E^{\prime})$ of
$H({\mathcal{I}})$, that is defined as follows: $X^{\prime}=X^{*}$,
$Y^{\prime}=Y^{*}$, and $E^{\prime}=E^{*}$. We now verify that this graph has
all required properties.

Recall that, from 3.17,
$|X^{*}|\leq\frac{|\tilde{X}|}{2^{q}}\leq\frac{|X|}{2^{q}}$, from Corollary
3.18, $2^{q}\geq\frac{2^{r}}{2d(n)}$, and, from our assumption, $2^{r}>\beta$.
Therefore:

$|X^{*}|\leq\frac{|X|}{2^{q}}\leq\frac{|X|\cdot
2d(n)}{2^{r}}\leq\frac{2d(n)}{\beta}\cdot|X|.$

Similarly, from 3.17,
$|Y^{*}|\leq\frac{|\tilde{Y}|}{2^{q^{\prime}}}\leq\frac{|Y|}{2^{q^{\prime}}}$,
from Corollary 3.18, $2^{q^{\prime}}\geq\frac{2^{r}}{2d(n)}$, and, from our
assumption, $2^{r}>\beta$. Therefore:

$|Y^{*}|\leq\frac{|Y|}{2^{q^{\prime}}}\leq\frac{|Y|\cdot
2d(n)}{2^{r}}\leq\frac{2d(n)}{\beta}\cdot|Y|.$

It now only remains to show that
$|E^{*}|\geq\frac{\operatorname{vol}_{H}(X^{*}\cup
Y^{*})}{256d(n)\cdot\alpha(n)\cdot\log^{4}n}$.

Recall that, from Inequality 2,
$|\mathcal{C}^{*}|\geq\frac{d_{1}\cdot|\tilde{X}|}{2^{r+8}\cdot\alpha(n)\cdot\log^{4}n}$
holds. Since, from Corollary 3.18, $2^{r}\leq 2^{q}\cdot 2d(n)$, we get that
$|E^{*}|=|\mathcal{C}^{*}|\geq\frac{d_{1}\cdot|\tilde{X}|}{2^{q+9}\cdot
d(n)\cdot\alpha(n)\cdot\log^{4}n}$. At the same time, from the definition of a
nice graph, for every vertex $x\in X^{*}$, $\deg_{H}(x)\leq 2d_{1}$, so
$\operatorname{vol}_{H}(X^{*})\leq
2d_{1}\cdot|X^{*}|\leq\frac{2d_{1}\cdot|\tilde{X}|}{2^{q}}$, since
$|X^{*}|\leq\frac{|\tilde{X}|}{2^{q}}$ from 3.17. Therefore,
$|E^{\prime}|\geq\frac{\operatorname{vol}_{H}(X^{*})}{1024d(n)\cdot\alpha(n)\cdot\log^{4}n}$.

Similarly, from Inequality 1,
$|\mathcal{C}^{*}|\geq\frac{d_{2}\cdot|\tilde{Y}|}{2^{r+6}\cdot\alpha(n)\cdot\log^{3}n}$.
Since, from Corollary 3.18, $2^{r}\leq 2^{q^{\prime}}\cdot 2d(n)$, we get that
$|E^{\prime}|=|\mathcal{C}^{*}|\geq\frac{d_{2}\cdot|\tilde{Y}|}{2^{q^{\prime}+7}\cdot
d(n)\cdot\alpha(n)\cdot\log^{3}n}$. At the same time, from the definition of a
nice graph, for every vertex $y\in Y^{*}$, $\deg_{H}(y)\leq 2d_{2}$, so
$\operatorname{vol}_{H}(Y^{*})\leq
2d_{2}\cdot|Y^{*}|\leq\frac{2d_{2}\cdot|\tilde{Y}|}{2^{q^{\prime}}}$, since
$|Y^{*}|\leq\frac{|\tilde{Y}|}{2^{q^{\prime}}}$ from 3.17. Therefore,
$|E^{*}|\geq\frac{\operatorname{vol}_{H}(Y^{*})}{1024d(n)\cdot\alpha(n)\cdot\log^{3}n}$.

Altogether, we get that
$|E^{\prime}|\geq\frac{\operatorname{vol}_{H}(X^{*}\cup
Y^{*})}{2048d(n)\cdot\alpha(n)\cdot\log^{4}n}$.

Note that every step of the algorithm, except Step 2, has running time
$O(\textnormal{poly}(n))$, while the running time of Step 2 is
$O(T(n)+\textnormal{poly}(n))$. Therefore, the total running time of the
algorithm is at most $O(T(n)\cdot\textnormal{poly}(n))$.

##  4 Reductions from Dense $k$-Coloring and (r,h)-Graph Partitioning to
Densest $k$-Subgraph

In this section we provide reductions from the Dense $k$-Coloring and
(r,h)-Graph Partitioning problems to Densest $k$-Subgraph, by proving the
following theorem.

######  Theorem 4.1.

Let $\alpha:\mathbb{Z^{+}}\to\mathbb{Z^{+}}$ be an increasing function, such
that $\alpha(n)\leq o(n)$. Assume 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. Then both of the
following hold:

  * •

there is an efficient randomized algorithm that, given an instance of Dense
$k$-Coloring whose graph contains $N$ vertices, with high probability computes
an $O(\alpha(N^{2})\cdot\textnormal{poly}\log N)$-approximate solution to this
instance; and

  * •

there is an efficient randomized algorithm that, given an instance of
(r,h)-Graph Partitioning whose graph contains $N$ vertices, with high
probability computes an $O(\alpha(N^{2})\cdot\textnormal{poly}\log
N)$-approximate solution to this instance.

We provide the proof of the first assertion of the theorem, by showing a
reduction from Dense $k$-Coloring to Densest $k$-Subgraph. The proof of the
second assertion is similar and is deferred to Section B of Appendix. We start
by considering an LP-relaxation of the Dense $k$-Coloring problem, whose
number of variables is at least $N\choose k$. Due to this high number of
variables, we cannot solve it directly. We first show an algorithm, that,
given an approximate fractional solution to this LP-relaxation, whose support
size is polynomial in $N$, computes an approximate integral solution to the
Dense $k$-Coloring problem instance. We then show an efficient algorithm that
computes an approximate solution to the LP-relaxation, whose support is
relatively small. In order to do so, we design an approximate separation
oracle to the dual LP of the LP-relaxation.

###  4.1 An LP-Relaxation and Its Rounding

Let $\mathrm{DkC}(G,k)$ be an input instance of the Dense $k$-Coloring
problem, and denote $|V(G)|=N$. We let ${\mathcal{R}}$ the collection of all
subsets of $V(G)$ containing at most $k$ vertices, that is:
${\mathcal{R}}=\\{S\subseteq V(G)\mid|S|\leq k\\}$. For every set
$S\in{\mathcal{R}}$ of vertices, we denote by $m(S)=|E_{G}(S)|$. We consider
the following LP-relaxation of the Dense $k$-Coloring problem, that has a
variable $x_{S}$ for every set $S\in{\mathcal{R}}$ of vertices.

(LP-P) $\displaystyle\max$ $\displaystyle\sum_{S\in{\mathcal{R}}}m(S)\cdot
x_{S}$ s.t. $\displaystyle\sum_{\stackrel{{\scriptstyle
S\in{\mathcal{R}}:}}{{v\in S}}}x_{S}\leq 1$ $\displaystyle\forall v\in V(G)$
$\displaystyle\sum_{S\in{\mathcal{R}}}x_{S}\leq N/k$ $\displaystyle x_{S}\geq
0$ $\displaystyle\forall S\in{\mathcal{R}}$

It is easy to verify that (LP-P) is an LP-relaxation of the Dense $k$-Coloring
problem. Indeed, consider a solution $(S_{1},\ldots,S_{r})$ to the input
instance $\mathrm{DkC}(G,k)$, where $r=N/k$. For all $1\leq i\leq r$, we set
$x_{S_{i}}=1$, and for every other set $S\in{\mathcal{R}}$, we set $x_{S}=0$.
This provides a feasible solution to (LP-P), whose value is precisely
$\sum_{i=1}^{r}|E_{G}(S_{i})|$. We denote the value of the optimal solution to
(LP-P) by $\text{OPT}_{\textnormal{LP-P}}$. From the above discussion,
$\text{OPT}_{\textnormal{LP-P}}\geq\mathrm{OPT_{DkC}}(G,k)$.

Note that the number of variables in (LP-P) is at least $N\choose k$, and so
we cannot solve it directly. We will show below an efficient algorithm that
provides an approximate solution to (LP-P), whose support is reasonably small.
Before we do so, we provide an LP-rounding algorithm, by proving the following
claim.

######  Claim 4.2.

There is an efficient randomized algorithm, whose input consists of an
instance $\mathrm{DkC}(G,k)$ of the Dense $k$-Coloring problem with
$N=|V(G)|$, such that $N$ is greater than a large enough constant, and a
solution $\\{x_{S}\mid S\in{\mathcal{R}}\\}$ to (LP-P), in which the number of
variables $x_{S}$ with $x_{S}>0$ is bounded by $\textnormal{poly}(N)$, and
$\sum_{S\in{\mathcal{R}}}m(S)\cdot
x_{S}\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_{S}$ that are non-zero. The algorithm with high probability
returns an integral solution $(S_{1},\ldots,S_{N/k})$ to instance
$\mathrm{DkC}(G,k)$, such that
$\sum_{i=1}^{N/k}|E_{G}(S_{i})|\geq\frac{\mathrm{OPT_{DkC}}(G,k)}{2000\beta\log^{3}N}$.

Proof: We assume that we are given a solution $\\{x_{S}\mid
S\in{\mathcal{R}}\\}$ to (LP-P), in which the number of variables $x_{S}$ with
$x_{S}>0$ is bounded by $\textnormal{poly}(N)$. Denote
$C=\sum_{S\in{\mathcal{R}}}m(S)\cdot x_{S}$, so that
$C\geq\frac{\text{OPT}_{\textnormal{LP-P}}}{\beta}\geq\frac{\mathrm{OPT_{DkC}}(G,k)}{\beta}$
holds. We denote by ${\mathcal{R}}^{\prime}\subseteq{\mathcal{R}}$ the
collection of all sets $S\in{\mathcal{R}}$ with $x_{S}>0$. Assume first that
there is any set $S\in{\mathcal{R}}^{\prime}$ with
$m(S)\geq\frac{C}{300\log^{3}N}$. Then we can obtain the desired solution
$(S_{1},\ldots,S_{N/k})$ as follows. We start with $S_{1}=S$ and
$S_{2}=\cdots=S_{N/k}=\emptyset$. We then iteratively add vertices of
$V(G)\setminus S$ to sets $S_{1},\ldots,S_{N/k}$ arbitrarily, to ensure that
the cardinality of each such set is exactly $k$. It is immediate to verify
that
$\sum_{i=1}^{N/k}|E_{G}(S_{i})|\geq\frac{C}{300\log^{3}N}\geq\frac{\mathrm{OPT_{DkC}}(G,k)}{300\beta\log^{3}N}$.
Therefore, we assume from now on that, for every set
$S\in{\mathcal{R}}^{\prime}$, $m(S)<\frac{C}{300\log^{3}N}$.

We construct another collection
${\mathcal{R}}^{\prime\prime}\subseteq{\mathcal{R}}^{\prime}$ of subsets of
vertices of $G$ as follows. For every set $S\in{\mathcal{R}}^{\prime}$, we add
$S$ to ${\mathcal{R}}^{\prime\prime}$ independently, with probability $x_{S}$.
Clearly, $\text{\bf
E}\left[\sum_{S\in{\mathcal{R}}^{\prime\prime}}m(S)\right]=\sum_{S\in{\mathcal{R}}}m(S)\cdot
x_{S}=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$ sets in ${\mathcal{R}}^{\prime\prime}$. We say
that a bad event ${\cal{E}}_{2}$ happens if
$|{\mathcal{R}}^{\prime\prime}|>(5N\log N)/k$. We say that a bad event
${\cal{E}}_{3}$ happens if
$\sum_{S\in{\mathcal{R}}^{\prime\prime}}m(S)<\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. We start with the
following simple observation.

######  Observation 4.3.

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

Proof: For every set $S\in{\mathcal{R}}^{\prime}$, let $Y_{S}$ be the random
variable whose value is $1$ if $S\in{\mathcal{R}}^{\prime\prime}$ and $0$
otherwise.

Consider any vertex $v\in V(G)$. Denote by $Z_{v}$ the number of vertex sets
in ${\mathcal{R}}^{\prime\prime}$ containing $v$. Clearly,
$Z_{v}=\sum_{\stackrel{{\scriptstyle S\in{\mathcal{R}}^{\prime}:}}{{v\in
S}}}Y_{S}$. Therefore:

$\text{\bf E}\left[Z_{v}\right]=\text{\bf
E}\left[\sum_{\stackrel{{\scriptstyle S\in{\mathcal{R}}^{\prime}:}}{{v\in
S}}}Y_{S}\right]=\sum_{\stackrel{{\scriptstyle
S\in{\mathcal{R}}^{\prime}:}}{{v\in S}}}x_{S}\leq 1,$

where the last inequality follows from the constraints of (LP-P).

By applying the Chernoff Bound from Lemma 2.2, we get that $\text{\bf
Pr}\left[Z_{v}>5\log N\right]\leq 1/N^{5}$. Using the union bound over all
vertices $v\in V(G)$, we get that $\text{\bf Pr}\left[{\cal{E}}_{1}\right]\leq
1/N^{4}$.

Notice that $\text{\bf E}\left[|{\mathcal{R}}^{\prime\prime}|\right]=\text{\bf
E}\left[\sum_{S\in{\mathcal{R}}}Y_{S}\right]=\sum_{S\in{\mathcal{R}}}x_{S}\leq
N/k$ from the constraints of (LP-P). Bad Event ${\cal{E}}_{2}$ happens if
$|{\mathcal{R}}^{\prime\prime}|=\sum_{S\in{\mathcal{R}}}Y_{S}>(5N\log N)/k$.
By applying the Chernoff Bound from Lemma 2.2 to the variables of
$\\{Y_{S}\mid S\in{\mathcal{R}}^{\prime}\\}$, we get that $\text{\bf
Pr}\left[{\cal{E}}_{2}\right]=\text{\bf
Pr}\left[\sum_{S\in{\mathcal{R}}^{\prime}}Y_{S}>(5N\log N)/k\right]\leq
1/N^{5}$.

Lastly, we bound the probability of Event ${\cal{E}}_{3}$. Recall that we have
assumed that, for every set $S\in{\mathcal{R}}^{\prime}$,
$m(S)<\frac{C}{300\log^{3}N}$ holds. We partition the collection
${\mathcal{R}}^{\prime}$ of vertex subsets into $\rho=\left\lceil 2\log
N\right\rceil$ collections ${\mathcal{R}}_{0},\ldots,{\mathcal{R}}_{\rho-1}$,
as follows. For all $0\leq i<\rho$, we let
${\mathcal{R}}_{i}=\\{S\in{\mathcal{R}}^{\prime}\mid 2^{i}\leq
m(S)<2^{i+1}\\}$. For all $0\leq i<\rho$, we denote
$C_{i}=\sum_{S\in{\mathcal{R}}_{i}}m(S)\cdot x_{S}$. Clearly,
$\sum_{i=0}^{\rho-1}C_{i}=C$. We say that an index $0\leq i<\rho$ is _bad_ ,
if $C_{i}<\frac{C}{8\log N}$, and otherwise we say that $i$ is a _good index_.
Let $I^{g},I^{b}\subseteq\\{0,\ldots,\rho-1\\}$ be the collections of good and
bad indices, respectively. Since $\rho\leq 4\log N$, we get that:

$\sum_{i\in I^{b}}C_{i}\leq(4\log N)\cdot\frac{C}{8\log N}\leq\frac{C}{2}.$

Therefore, $\sum_{i\in I^{g}}C_{i}\geq\frac{C}{2}$ holds. Consider now a good
index $i\in I^{g}$. Recall that, for every set $S\in{\mathcal{R}}^{\prime}$,