Introduction
Identifying dense bipartite subgraphs is a fundamental primitive across machine learning, network science, and web data mining. Bipartite graphs model interactions between two kinds of entities: accounts and products in e-commerce, users and multimedia content on social platforms, authors and venues in bibliometrics, or queries and destination URLs in web search [12 ] . In fraud detection and cybersecurity, researchers search for dense bipartite subgraphs to detect botnets, astroturfing campaigns, and lockstep review manipulation, where malicious actors coordinate attacks against targeted subsets of resources [7 , 20 , 16 , 35 ] . In web mining, dense subgraphs correspond to link-spam farms [15 ] and authoritative topic hubs [22 ] . In computational biology, dense subgraphs are used to identify regulatory motifs in genomic DNA [14 ] , analyze drug–target interaction graphs, and uncover multi-functional complexes in gene annotation networks [34 ] .
To quantify how tightly two sets of vertices are connected, we use the bipartite density objective [21 , 2 ] . Throughout, G = ( V , E ) G=(V,E) G = ( V , E ) is a finite simple undirected bipartite graph with a fixed bipartition V = L ∪ ˙ R V=L\mathbin{\dot\cup}R V = L ∪ ˙ R and maximum degree Δ \Delta Δ . For nonempty vertex sets S ⊆ L S\subseteq L S ⊆ L and T ⊆ R T\subseteq R T ⊆ R with e ( S , T ) e(S,T) e ( S , T ) edges between them, their density is
d ( S , T ) : = e ( S , T ) ∣ S ∣ ∣ T ∣ = e ( S , T ) ∣ S ∣ ⋅ e ( S , T ) ∣ T ∣ , d(S,T):=\frac{e(S,T)}{\sqrt{|S||T|}}=\sqrt{\frac{e(S,T)}{|S|}\cdot\frac{e(S,T)}{|T|}}, d ( S , T ) := ∣ S ∣∣ T ∣ e ( S , T ) = ∣ S ∣ e ( S , T ) ⋅ ∣ T ∣ e ( S , T ) ,
the geometric mean of the average degree from S S S into T T T and the average degree from T T T into S S S .
The maximum of d ( S , T ) d(S,T) d ( S , T ) over all nonempty sets S , T S,T S , T on opposite sides can be computed in polynomial time by linear programming [9 ] . However, on modern web-scale networks—frequently spanning hundreds of millions of vertices and billions of edges [33 ] —such global algorithms are computationally prohibitive, as their running time and memory footprint scale with the size of the entire graph. We therefore study the local formulation [2 ] : given a starting vertex v v v and a target size parameter k k k , find a dense bipartite subgraph in the vicinity of v v v using a number of queries and running time that depend solely on k k k , completely independent of the graph size ∣ V ∣ |V| ∣ V ∣ and maximum degree Δ \Delta Δ .
Classical local clustering algorithms for low-conductance sets [36 , 3 , 1 ] seek sets with few boundary edges relative to their total degree. In contrast, d ( S , T ) d(S,T) d ( S , T ) is independent of edges leaving S ∪ T S\cup T S ∪ T . Dense bipartite subgraphs in interaction graphs often have many edges to the rest of the graph—for example, when fraudulent accounts add large numbers of legitimate interactions as “camouflage” [16 ] . With these camouflage edges, the cut conductance of S ∪ T S\cup T S ∪ T can approach 1. Standard random-walk and diffusion methods can then quickly leave the target, so we need local algorithms designed specifically for the bipartite density objective (see Figure 1 ).
Figure 1. A complete bipartite subgraph ( S , T ) (S,T) ( S , T ) with k k k vertices in S S S (blue) and k k k in T T T (orange), each with D ≥ 1 D \ge1 D ≥ 1 leaves (gray) outside S ∪ T S \cup T S ∪ T . Here d ( S , T ) = k d(S,T)=k d ( S , T ) = k for every D D D . Each vertex of S ∪ T S \cup T S ∪ T has D D D of its k + D k+D k + D edges leaving S ∪ T S \cup T S ∪ T , so the conductance of S ∪ T S \cup T S ∪ T is at least D / ( k + D ) D/(k+D) D / ( k + D ) , which tends to one as D / k → ∞ D/k \to\infty D / k → ∞ . Every star in this graph has density at most k + D \sqrt{k}+D k + D , which is o ( k ) o(k) o ( k ) for D = o ( k 2 ) D=o(k^2) D = o ( k 2 ) .
More formally, the local algorithm receives a starting vertex v v v , an integer k ≥ 1 k\geq1 k ≥ 1 , and adjacency-list access to G G G , as in Andersen [2 ] . We count neighbor queries: we read a specified entry of an adjacency list, or receive ⊥ \perp ⊥ past its end. The guarantee is measured against unknown cohesive sets S ⊆ L S\subseteq L S ⊆ L , T ⊆ R T\subseteq R T ⊆ R (Definition 1.1) with at most k k k vertices on each side. We require the algorithm to succeed from every starting vertex in S ∪ T S\cup T S ∪ T , using a number of queries independent of ∣ V ∣ |V| ∣ V ∣ . An approximation ratio α ≥ 1 \alpha\geq1 α ≥ 1 means returning nonempty sets X ⊆ L X\subseteq L X ⊆ L , Y ⊆ R Y\subseteq R Y ⊆ R with d ( X , Y ) ≥ d ( S , T ) / α d(X,Y)\geq d(S,T)/\alpha d ( X , Y ) ≥ d ( S , T ) / α . For a single vertex, we write e ( u , T ) : = e ( { u } , T ) e(u,T):=e(\{u\},T) e ( u , T ) := e ({ u } , T ) and e ( S , w ) : = e ( S , { w } ) e(S,w):=e(S,\{w\}) e ( S , w ) := e ( S , { w }) .
We ask for approximation, not recovery: the union of the returned sets need not contain the starting vertex or intersect S ∪ T S\cup T S ∪ T (after adding v v v to the returned set on its side, the density is at least d ( X , Y ) / 2 d(X,Y)/\sqrt{2} d ( X , Y ) / 2 ; see Lemma B.3). A star with at least d ( S , T ) 2 d(S,T)^2 d ( S , T ) 2 leaves has density at least d ( S , T ) d(S,T) d ( S , T ) and is therefore an acceptable output.
Andersen’s algorithm can be implemented using O ( Δ k 2 ) O(\Delta k^2) O ( Δ k 2 ) neighbor queries and returns sets X , Y X,Y X , Y with O ( Δ k 2 ) O(\Delta k^2) O ( Δ k 2 ) vertices each (this follows from Andersen’s analysis Andersen [2 ] ; see also Appendix § 9 .§ 2 ). Its approximation ratio is bounded by O ( 1 + log 2 ( Δ / d ( S , T ) ) ) O(1+\log_2(\Delta/d(S,T))) O ( 1 + log 2 ( Δ/ d ( S , T ))) Andersen [2 ] . This bound is constant only when d ( S , T ) = Ω ( Δ ) d(S,T)=\Omega(\Delta) d ( S , T ) = Ω ( Δ ) . For the complete bipartite subgraph of Figure 1 with D D D camouflage edges per vertex, the lower bound on the returned density is Ω ( k / ( 1 + log 2 ( ( k + D ) / k ) ) ) \Omega(k/(1+\log_2((k+D)/k))) Ω ( k / ( 1 + log 2 (( k + D ) / k ))) , which decreases as D D D grows even though d ( S , T ) = k d(S,T)=k d ( S , T ) = k . The density is invariant under the addition of edges outside the subgraph induced by S ∪ T S \cup T S ∪ T , and the guarantee is not. Whether this dependence on the maximum degree is necessary for local approximation was open.
Our results
Our main result is a constant-factor local approximation algorithm for the bipartite densest subgraph problem. We cannot guarantee success from every vertex of S ∪ T S \cup T S ∪ T for arbitrary target sets S , T S,T S , T , since a vertex in S ∪ T S \cup T S ∪ T may have few or no edges into the opposite target set. We therefore require every target vertex to have at least half the average degree of its side within the target subgraph.
Definition 1.1 (Cohesive sets). Nonempty sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R with e ( S , T ) > 0 e(S,T)>0 e ( S , T ) > 0 are cohesive if e ( u , T ) ≥ e ( S , T ) 2 ∣ S ∣ e(u,T) \ge\frac{e(S,T)}{2|S|} e ( u , T ) ≥ 2∣ S ∣ e ( S , T ) for all u ∈ S u \in S u ∈ S , and e ( S , w ) ≥ e ( S , T ) 2 ∣ T ∣ e(S,w) \ge\frac{e(S,T)}{2|T|} e ( S , w ) ≥ 2∣ T ∣ e ( S , T ) for all $w \in T.
We use the term cohesiveness to formalize the minimum-degree structure already implicit in Andersen’s proof of his main theorem Andersen [2 ] . For any sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R with e ( S , T ) > 0 e(S,T)>0 e ( S , T ) > 0 , there are cohesive subsets S ∗ ⊆ S S^* \subseteq S S ∗ ⊆ S , T ∗ ⊆ T T^* \subseteq T T ∗ ⊆ T of at least the same density, d ( S ∗ , T ∗ ) ≥ d ( S , T ) d(S^*,T^*) \ge d(S,T) d ( S ∗ , T ∗ ) ≥ d ( S , T ) (Lemma A.1 ). For arbitrary S , T S,T S , T , our setting is exactly that of Andersen, whose algorithm succeeds from every vertex of subsets that are selected by a minimum-degree argument and contain at least half of the edges (see the discussion in Corollary A.2 ).
Theorem 1.2 (Main result). For every ϵ > 0 \epsilon> 0 ϵ > 0 , all cohesive sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R with ∣ S ∣ , ∣ T ∣ ≤ k |S|, |T| \le k ∣ S ∣ , ∣ T ∣ ≤ k , and every starting vertex v ∈ S ∪ ˙ T v \in S \mathbin{\dot\cup} T v ∈ S ∪ ˙ T , the deterministic algorithm LocalDense2 + ϵ ( G , v , k ) _{2+\epsilon}(G, v, k) 2 + ϵ ( G , v , k ) (Algorithm 2 ) returns nonempty sets X ⊆ L X \subseteq L X ⊆ L , Y ⊆ R Y \subseteq R Y ⊆ R with the following guarantees:
(i) Locality and complexity: The output ( X , Y ) (X,Y) ( X , Y ) has O ϵ ( k 2 + ϵ ) O_\epsilon(k^{2+\epsilon}) O ϵ ( k 2 + ϵ ) vertices, and the algorithm makes O ϵ ( k 2 + ϵ min { Δ log 2 2 ( 2 k ) , k 2 } ) O_\epsilon(k^{2+\epsilon}\min\{\Delta\log_2^2(2k), k^2\}) O ϵ ( k 2 + ϵ min { Δ log 2 2 ( 2 k ) , k 2 }) neighbor queries and runs in time O ~ ϵ ( k 2 + ϵ min { Δ , k 2 } ) \widetilde{O}_\epsilon(k^{2+\epsilon}\min\{\Delta, k^2\}) O ϵ ( k 2 + ϵ min { Δ , k 2 }) .
(ii) Constant-factor approximation: d ( X , Y ) ≥ 3 16 e ϵ 1 + ϵ d ( S , T ) d(X,Y) \ge\frac{\sqrt{3}}{16\sqrt{e}}\frac{\epsilon}{1+\epsilon}d(S,T) d ( X , Y ) ≥ 16 e 3 1 + ϵ ϵ d ( S , T ) , independent of edges outside the subgraph induced by S ∪ ˙ T S \mathbin{\dot\cup} T S ∪ ˙ T .
We complement our positive results by proving limitations on the output size:
Theorem 1.3 (Limitations on the output size, informal). No possibly randomized algorithm with neighbor-query access that, for all cohesive sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R with k k k vertices on each side, returns nonempty sets X ⊆ L X \subseteq L X ⊆ L , Y ⊆ R Y \subseteq R Y ⊆ R with d ( X , Y ) = Ω ( d ( S , T ) ) d(X,Y)=\Omega(d(S,T)) d ( X , Y ) = Ω ( d ( S , T )) with probability at least 2 / 3 2/3 2/3 from at least one vertex in S ∪ ˙ T S \mathbin{\dot\cup} T S ∪ ˙ T can guarantee an output bound of o ( k 2 ) o(k^2) o ( k 2 ) vertices on each side if either:
(i) Unconditional: Its number of queries depends only on k k k ; or
(ii) Computational: Assuming the Strongish Planted Clique Hypothesis (SPCH), its running time is at most f ( k ) ∣ V ∣ c f(k)|V|^c f ( k ) ∣ V ∣ c for a constant c c c and a computable function f f f of k k k alone.
Up to the factor k ϵ k^\epsilon k ϵ , our output size is therefore the best possible in both settings. We discuss the main result in § 2 and the limitations in § 3 .
Our technique
From power iteration to prefix sweeps. Our starting point is Andersen’s pruned power iteration [2 ] . We maintain a nonnegative vector x x x indexed by vertices and multiply it by the adjacency matrix, setting y ( w ) : = ∑ u x ( u ) y(w) := \sum_u x(u) y ( w ) := ∑ u x ( u ) , where the sum is over the neighbors of w w w . For now, we set aside rescaling and pruning. The mass of x x x on a set Q Q Q is ∑ u ∈ Q x ( u ) \sum_{u\in Q}x(u) ∑ u ∈ Q x ( u ) . Suppose every vertex of S S S has at least a a a neighbors in T T T and every vertex of T T T at least b b b in S S S . After one multiplication, the mass of y y y on T T T is at least a a a times the mass of x x x on S S S , and after two, the mass on S S S is at least a b ab ab times its original value. These bounds hold even with edges leaving the target, since all coordinates are nonnegative. By cohesiveness, there exist powers of two a , b ∈ [ 1 , k ] a,b\in[1,k] a , b ∈ [ 1 , k ] , with a b > d ( S , T ) / 4 \sqrt{ab}>d(S,T)/4 ab > d ( S , T ) /4 (see § 2.2 ; we remove this choice later). We cannot locate a dense pair from the growth of target mass alone: the target is unknown, and mass outside it may grow faster. Andersen extracts a dense pair from growth of the Euclidean norm. Instead we sort consecutive vectors and consider their initial segments, or prefixes . We seek a Lovász–Simonovits-type win–win [36 , 3 ] : either we find a dense prefix pair in a sweep, or we obtain upper bounds on prefix sums that eventually become incompatible with the mass that remains on the target. Here set size means number of vertices, rather than volume.
The choice of norm. Which bound on prefix sums should we use for this alternative? Write P i ( x ) P_i(x) P i ( x ) for the vertices with the i i i largest positive coordinates, breaking ties by identifier, and I x ( m ) : = max ∣ Q ∣ ≤ m ∑ u ∈ Q x ( u ) I_x(m):=\max_{|Q|\le m}\sum_{u\in Q}x(u) I x ( m ) := max ∣ Q ∣ ≤ m ∑ u ∈ Q x ( u ) . A natural choice is the Euclidean norm, since I x ( m ) ≤ ∥ x ∥ 2 m I_x(m)\le\|x\|_2\sqrt{m} I x ( m ) ≤ ∥ x ∥ 2 m . However, with only this inequality we incur a logarithmic loss when summing comparable bounds over dyadic ranges of prefix sizes (see § 2.1 ). Changing the sweep alone is therefore not enough. We instead fix p > 2 p>2 p > 2 and use the weak-ℓ p \ell_p ℓ p norm [6 Chapter 4]
∥ x ∥ p , ∞ : = sup m ∈ { 1 , 2 , … } I x ( m ) m 1 − 1 / p . \|x\|_{p,\infty}:=\sup_{m\in\{1,2,\ldots\}}\frac{I_x(m)}{m^{1-1/p}}. ∥ x ∥ p , ∞ := m ∈ { 1 , 2 , … } sup m 1 − 1/ p I x ( m ) .
The bounds over dyadic ranges now form a geometric series, so we incur only a p p p -dependent factor when summing them (a detailed explanation of this comparison can be found in Appendix § 9 .§ 3 ). More precisely, let y = x A y=xA y = x A , where x ≥ 0 x \ge0 x ≥ 0 is supported on L L L and A A A is an L × R L \times R L × R adjacency matrix with column sums at most B ∞ B_\infty B ∞ . Let σ > 0 \sigma> 0 σ > 0 be the density we aim to guarantee in the returned sets. For a prefix P m ( y ) P_m(y) P m ( y ) , if d ( P i ( x ) , P m ( y ) ) ≤ σ d(P_i(x),P_m(y)) \le\sigma d ( P i ( x ) , P m ( y )) ≤ σ for every prefix P i ( x ) P_i(x) P i ( x ) , then
I y ( m ) ≤ C p σ 2 / p B ∞ 1 − 2 / p ∥ x ∥ p , ∞ m 1 − 1 / p , C p : = p − 1 p − 2 . I_y(m) \le C_p \sigma^{2/p} B_\infty^{1-2/p} \lVert x\rVert_{p,\infty}m^{1-1/p}, \qquad C_p := \frac{p-1}{p-2}. I y ( m ) ≤ C p σ 2/ p B ∞ 1 − 2/ p ∥ x ∥ p , ∞ m 1 − 1/ p , C p := p − 2 p − 1 .
If the inequality fails for P m ( y ) P_m(y) P m ( y ) , we find dense sets by sweeping the prefixes of x x x against P m ( y ) P_m(y) P m ( y ) . If no prefixes exceed density σ \sigma σ , we take the supremum over m m m to bound ∥ y ∥ p , ∞ \lVert y\rVert_{p,\infty} ∥ y ∥ p , ∞ (§ 2.1 and Appendix § 7 .§ 3 ).
Removing the degree dependence. The logarithm is gone, but the column sums remain. For the full adjacency matrix, we only know the bound B ∞ = Δ B_\infty= \Delta B ∞ = Δ on the column sums, where Δ \Delta Δ is the maximum degree. Since a b > d ( S , T ) / 4 \sqrt{ab} > d(S,T)/4 ab > d ( S , T ) /4 , we obtain a constant-factor approximation if we can guarantee density σ \sigma σ equal to a fixed fraction of a b \sqrt{ab} ab , depending only on p p p . The upper bound on the norm after two steps has factor C p 2 σ 4 / p Δ 2 − 4 / p C_p^2\sigma^{4/p}\Delta^{2-4/p} C p 2 σ 4/ p Δ 2 − 4/ p , compared with the factor a b ab ab for the mass on S S S . To make the norm factor smaller than a b ab ab , we need σ < C p − p / 2 a b ( a b / Δ ) ( p − 2 ) / 2 \sigma< C_p^{-p/2}\sqrt{ab}(\sqrt{ab}/\Delta)^{(p-2)/2} σ < C p − p /2 ab ( ab /Δ ) ( p − 2 ) /2 , at the cost of an additional approximation factor ( Δ / a b ) ( p − 2 ) / 2 (\Delta/\sqrt{ab})^{(p-2)/2} ( Δ/ ab ) ( p − 2 ) /2 .
After rescaling, we want the target mass to grow while the weak norm decreases over pairs of steps. For a step from L L L to R R R , we use peeling to bound the number of selected edges incident to each vertex in R R R while keeping enough target edges. We repeatedly remove a vertex in R R R with at most b / 2 b/2 b /2 remaining edges and select those edges, or a vertex in the current support with at most a / 4 a/4 a /4 remaining edges and discard those edges. If vertices remain but neither removal is possible, their density exceeds a b / 8 \sqrt{ab}/8 ab /8 (§ 2.2 ). If every vertex is removed, each vertex in R R R has at most b / 2 b/2 b /2 selected edges, while at least 3 a / 4 3a/4 3 a /4 edges into T T T are selected at each vertex of S ∩ supp ( x ) S \cap\operatorname{supp}(x) S ∩ supp ( x ) . Let A A A be the adjacency matrix of the selected edges and set y = ( 2 / b ) x A y=(2/b)xA y = ( 2/ b ) x A , so that the weighted column sums are at most one. For σ : = 3 a b / ( 4 C p p / 2 ) \sigma:= \sqrt{3ab}/(4C_p^{p/2}) σ := 3 ab / ( 4 C p p /2 ) , we either find prefixes of density greater than σ \sigma σ , or
∑ w ∈ T y ( w ) ≥ 3 a 2 b ∑ u ∈ S x ( u ) , ∥ y ∥ p , ∞ ≤ ( 3 a 4 b ) 1 / p ∥ x ∥ p , ∞ . \sum_{w \in T} y(w) \ge\frac{3a}{2b}\sum_{u \in S}x(u), \qquad\lVert y\rVert_{p,\infty} \le\left(\frac{3a}{4b}\right)^{1/p}\lVert x\rVert_{p,\infty}. w ∈ T ∑ y ( w ) ≥ 2 b 3 a u ∈ S ∑ x ( u ) , ∥ y ∥ p , ∞ ≤ ( 4 b 3 a ) 1/ p ∥ x ∥ p , ∞ .
For the reverse step, we exchange a a a and b b b . If no dense sets are returned in either step, then after two steps without pruning the mass on S S S is at least 9 / 4 9/4 9/4 times its earlier value, while the weak norm is at most ( 3 / 4 ) 2 / p (3/4)^{2/p} ( 3/4 ) 2/ p times its earlier value. Crucially, neither factor now depends on Δ \Delta Δ (§ 2.3 ).
The local search. We are now ready to combine the ideas above and present the algorithm. So far, we have assumed that suitable degree bounds a , b a,b a , b are known. In reality, since they are unknown, we run a search for every pair of powers of two, a , b ∈ [ 1 , k ] a,b \in[1,k] a , b ∈ [ 1 , k ] and return the densest candidate. Assume v ∈ L v \in L v ∈ L , exchanging the sides if necessary. Each search starts with x 0 = 1 v x_0=\mathbf{1}_v x 0 = 1 v , the vector equal to one at v v v and zero elsewhere, and alternates between the sides. At step t t t , the algorithm reads at most ⌈ σ 2 ⌉ \lceil\sigma^2\rceil ⌈ σ 2 ⌉ entries of the adjacency list of each vertex in supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) . If it finds that many neighbors in one list, it returns a star of density at least σ \sigma σ . If no star is returned, all these adjacency lists have been read completely. The algorithm then peels the edges incident to the support of x t x_t x t and, unless dense sets are returned, performs the rescaled multiplication and sets coordinates below δ \delta δ to zero. We choose δ \delta δ to keep the support small without losing too much target mass.
We abandon the guess if the pruned vector z z z is zero and otherwise set x t + 1 = z x_{t+1}=z x t + 1 = z only if its weak norm satisfies the bound from the inequalities above, which decreases over pairs of steps. If this bound is exceeded, we sweep x t x_t x t against the shortest prefix of z z z whose sum exceeds the corresponding bound. This prefix’s vertices and sum are unchanged by pruning, so we find dense sets.
For the degree bounds chosen using cohesiveness and v ∈ S v \in S v ∈ S , we measure target mass with a factor b / a b/a b / a on T T T and no factor on S S S . Before pruning, this mass is at least 3 / 2 3/2 3/2 times its previous value, and we choose δ \delta δ so that the loss during pruning is at most 1 / 2 1/2 1/2 . The weighted mass therefore stays at least one, its initial value, and the vector never becomes zero. At every even step reached by the search,
1 ≤ ∑ u ∈ S x t ( u ) ≤ ∥ x t ∥ p , ∞ k 1 − 1 / p ≤ ( 3 / 4 ) t / p k 1 − 1 / p . 1 \le\sum_{u \in S} x_t(u) \le\lVert x_t \rVert_{p,\infty} k^{1-1/p} \le(3/4)^{t/p} k^{1-1/p}. 1 ≤ u ∈ S ∑ x t ( u ) ≤ ∥ x t ∥ p , ∞ k 1 − 1/ p ≤ ( 3/4 ) t / p k 1 − 1/ p .
After O p ( log 2 ( 2 k ) ) O_p(\log_2(2k)) O p ( log 2 ( 2 k )) steps, the right-hand side would be less than one, so the search must return sets of density at least σ \sigma σ (§ 2.3 ).
Related Work
Spielman and Teng [36 ] used the Lovász–Simonovits curve ([26 , 27 ] ) to analyze their local partitioning algorithm Nibble, and Andersen et al. [3 ] adapted this analysis to personalized PageRank. Other local graph-partitioning algorithms use heat-kernel PageRank (Chung [10 ] ) or evolving sets (Andersen et al. [4 ] ), and local clustering by p p p -norm flow diffusions and p p p -norm cuts ([13 , 24 ] ) has been extended to vertex attributes and noisy labels ([37 , 5 ] ). Local algorithms for dense bipartite-like subgraphs ([31 , 23 , 28 ] ) minimize the bipartiteness ratio, a cut objective analogous to conductance.
Local and seeded variants of densest subgraph have also been studied from a practical perspective. When densest subgraphs are extracted sequentially, fragmented sub-regions of a single dominant global core may be returned while distinct local communities are missed. Qin et al. [33 ] therefore introduced locally densest subgraphs (LDS), based on ρ \rho ρ -compact subgraphs, with structural core bounds and pruning techniques for exact verification on billion-edge graphs, but their algorithm traverses the whole graph. Dai et al. [11 ] introduced the anchored densest subgraph (ADS) problem, with explicit edge or vertex penalties for expanding beyond a specified reference set, and solved it via localized parametric flow networks. Huang et al. [17 ] generalized this formulation to hypergraphs using negative submodular optimization, with strongly localized routines when the penalization parameter is sufficiently large. For dense-block discovery in fraud detection, Hooi et al. [16 ] gave a camouflage-resistant algorithm for the whole graph.
The local problem of Andersen [2 ] was revisited by Liu [25 ] , Theorems 1.2.2 and 1.2.3, who obtains an output size of O ( k 2 ) O(k^2) O ( k 2 ) with Andersen’s approximation ratio, and O ( k 1 + ϵ ) O(k^{1+\epsilon}) O ( k 1 + ϵ ) with a ratio that also depends on ∣ V ∣ |V| ∣ V ∣ . The techniques involved are different from ours and are based on spectral analysis, degree sorting, and majorization. Our algorithm, with ϵ = 1 / ⌈ log 2 ( 2 k ) ⌉ \epsilon= 1/\lceil\log_2(2k)\rceil ϵ = 1/ ⌈ log 2 ( 2 k )⌉ , also returns O ( k 2 ) O(k^2) O ( k 2 ) vertices, using O ( k 4 ) O(k^4) O ( k 4 ) neighbor queries with an O ( log 2 ( 2 k ) ) O(\log_2(2k)) O ( log 2 ( 2 k )) approximation ratio, independent of Δ \Delta Δ (Corollary B.4 ).
The local algorithm and its analysis
Our algorithm is based on an alternating power iteration from the starting vertex: with x 0 : = 1 v x_0 := \mathbb{1}_v x 0 := 1 v , it repeatedly multiplies the current vector by the adjacency matrix of a subgraph of G G G and then prunes, alternating between the two sides. For suitable degree guesses, the mass inside a cohesive target grows by a factor of at least 9 / 4 9/4 9/4 over two weighted steps, before accounting for pruning. The target is unknown to the algorithm, and the mass outside it may grow as well, so we cannot identify dense sets from growth alone. For the analysis, we compare prefixes: either prefixes P , Q P,Q P , Q of consecutive vectors have density d ( P , Q ) > σ d(P,Q)>\sigma d ( P , Q ) > σ and the algorithm returns them, or the next prefix sums are bounded in terms of the current ones, with geometrically decreasing bounds over pairs of steps. This cannot last forever: the target has at most k k k vertices per side, but its mass on the starting side stays at least one at every even step.
We use neighbor queries with fixed adjacency-list orders and distinct vertex identifiers. Vectors are row vectors indexed by vertices, with indicators 1 S \mathbf{1}_S 1 S , 1 v : = 1 { v } \mathbf{1}_v:=\mathbf{1}_{\{v\}} 1 v := 1 { v } and support supp ( x ) : = { u : x ( u ) ≠ 0 } \operatorname{supp}(x):=\{u:x(u)\ne0\} supp ( x ) := { u : x ( u ) = 0 } . Vectors are restricted or extended by zero to match matrix indices. For any subgraph H H H of G G G , numbers of edges and densities in H H H are denoted by e H ( S , T ) e_H(S,T) e H ( S , T ) and d H ( S , T ) d_H(S,T) d H ( S , T ) , and N G ( U ) N_G(U) N G ( U ) denotes the set of neighbors of U ⊆ V U\subseteq V U ⊆ V in G G G .
Prefix sweeps
In a step of the iteration from L L L to R R R , the current vector x ≥ 0 x\ge0 x ≥ 0 is supported on L L L and the next vector is y : = x A y:=xA y := x A , where A A A is the adjacency matrix of a subgraph of G G G , so that each coordinate y ( w ) y(w) y ( w ) is the sum of x ( u ) x(u) x ( u ) over the neighbors u u u of w w w in this subgraph. To compare the largest coordinates of y y y with those of x x x , we adapt the Lovász–Simonovits curve ([26 , 27 ] ) to density: in place of the curve we use I x ( m ) I_x(m) I x ( m ) , the largest mass of the current vector on m m m vertices, and in place of a sweep set of low conductance we look for prefixes P , Q P,Q P , Q with d ( P , Q ) > σ d(P,Q)>\sigma d ( P , Q ) > σ , where σ > 0 \sigma>0 σ > 0 is a density threshold, fixed in (4) .
Definition 2.1. (Prefix sums and the weak norm [Spielman and Teng, 2013, equation (3); Bennett and Sharpley, 1988, Chapter 4]). For a vector x ≥ 0 x\ge0 x ≥ 0 indexed by a finite set and ℓ : = ∣ supp ( x ) ∣ \ell:=|\operatorname{supp}(x)| ℓ := ∣ supp ( x ) ∣ , write x ( 1 ) , … , x ( ℓ ) x_{(1)},\ldots,x_{(\ell)} x ( 1 ) , … , x ( ℓ ) for its positive coordinates in nonincreasing order, with ties broken by identifier, and set x ( i ) : = 0 x_{(i)}:=0 x ( i ) := 0 for i > ℓ i>\ell i > ℓ . For 1 ≤ i ≤ ℓ 1\le i\le\ell 1 ≤ i ≤ ℓ , the prefix P i ( x ) P_i(x) P i ( x ) consists of the first i i i vertices in this order. For p ≥ 2 p\ge2 p ≥ 2 , the prefix sums and weak-ℓ p \ell_p ℓ p norm are defined by
I x ( m ) : = max ∣ P ∣ ≤ m ∑ u ∈ P x ( u ) = ∑ i = 1 m x ( i ) , ∥ x ∥ p , ∞ : = sup s > 0 I x ( s ) s 1 − 1 / p , (1) I_x(m):=\max_{|P|\le m}\sum_{u\in P}x(u)=\sum_{i=1}^{m}x_{(i)},\qquad\|x\|_{p,\infty}:=\sup_{s>0}\frac{I_x(s)}{s^{1-1/p}}, \tag*{(1)} I x ( m ) := ∣ P ∣ ≤ m max u ∈ P ∑ x ( u ) = i = 1 ∑ m x ( i ) , ∥ x ∥ p , ∞ := s > 0 sup s 1 − 1/ p I x ( s ) , (1)
where m m m is a nonnegative integer and I x I_x I x is extended to real arguments s ≥ 0 s\ge0 s ≥ 0 by linear interpolation between consecutive integers, with I x ( 0 ) = 0 I_x(0)=0 I x ( 0 ) = 0 . In particular, I x ( s ) ≤ ∥ x ∥ p , ∞ s 1 − 1 / p I_x(s)\le\|x\|_{p,\infty}s^{1-1/p} I x ( s ) ≤ ∥ x ∥ p , ∞ s 1 − 1/ p for every s > 0 s>0 s > 0 .
Definition 2.2. (Column-sum bound). A nonnegative matrix A A A has column-sum bound B ∞ B_\infty B ∞ if ∑ u A u w ≤ B ∞ \sum_u A_{uw}\le B_\infty ∑ u A u w ≤ B ∞ for every column w w w .
After sorting y y y , we take a prefix P m ( y ) P_m(y) P m ( y ) , whose sum is I y ( m ) I_y(m) I y ( m ) , and in a sweep we look for a prefix P i ( x ) P_i(x) P i ( x ) with d ( P i ( x ) , P m ( y ) ) > σ d(P_i(x),P_m(y))>\sigma d ( P i ( x ) , P m ( y )) > σ . If there is none, then there are at most σ i m \sigma\sqrt{im} σ im edges between P i ( x ) P_i(x) P i ( x ) and P m ( y ) P_m(y) P m ( y ) for every i i i . For p > 2 p>2 p > 2 and a column-sum bound B ∞ B_\infty B ∞ for A A A (Definition 2.2 ),
I y ( m ) ≤ C p σ 2 / p B ∞ 1 − 2 / p ∥ x ∥ p , ∞ m 1 − 1 / p , where C p : = p − 1 p − 2 . (2) I_y(m)\le C_p\sigma^{2/p}B_\infty^{1-2/p}\|x\|_{p,\infty}m^{1-1/p},\qquad\text{where }C_p:=\frac{p-1}{p-2}. \tag*{(2)} I y ( m ) ≤ C p σ 2/ p B ∞ 1 − 2/ p ∥ x ∥ p , ∞ m 1 − 1/ p , where C p := p − 2 p − 1 . (2)
This bound is a special case of Proposition A.4 , proved in Appendix § 7 .§ 3 by summation by parts. In the proof, we use the smaller of two bounds for the number of edges from P i ( x ) P_i(x) P i ( x ) into P m ( y ) P_m(y) P m ( y ) in the subgraph represented by A A A : σ i m \sigma\sqrt{im} σ im from the density assumption and B ∞ m B_\infty m B ∞ m from the column sums. Whenever I y ( m ) I_y(m) I y ( m ) exceeds the right side of (2), the algorithm finds a prefix P i ( x ) P_i(x) P i ( x ) with d ( P i ( x ) , P m ( y ) ) > σ d(P_i(x), P_m(y)) > \sigma d ( P i ( x ) , P m ( y )) > σ in the sweep. If no such prefixes exist for any m m m , then ∥ y ∥ p , ∞ ≤ C p σ 2 / p B ∞ 1 − 2 / p ∥ x ∥ p , ∞ \lVert y\rVert_{p,\infty} \le C_p \sigma^{2/p} B_\infty^{1-2/p}\lVert x\rVert_{p,\infty} ∥ y ∥ p , ∞ ≤ C p σ 2/ p B ∞ 1 − 2/ p ∥ x ∥ p , ∞ .
The bound holds only for p > 2 p > 2 p > 2 : for p = 2 p = 2 p = 2 , we obtain a logarithmic factor in place of C p C_p C p , as in the guarantee of Andersen [2 ] , to which we compare ours in Appendix § 9 . For the adjacency matrix of G G G itself, whose column sums are the degrees, we can only take B ∞ : = Δ B_\infty:= \Delta B ∞ := Δ , so that the bound contains a factor Δ 1 − 2 / p \Delta^{1-2/p} Δ 1 − 2/ p , even though d ( S , T ) d(S,T) d ( S , T ) is independent of edges outside the subgraph induced by S ∪ ˙ T S \mathbin{\dot\cup} T S ∪ ˙ T . To keep σ \sigma σ a fixed fraction of d ( S , T ) d(S,T) d ( S , T ) , we therefore need to bound B ∞ B_\infty B ∞ independently of Δ \Delta Δ .
Vertex peeling
For each multiplication, we select edges by peeling: we repeatedly remove a vertex of low degree, selecting its remaining edges if it is on the side of the next vector, so that its column sum is small, and discarding them if it is on the side of the current vector, so that only a few of its edges are discarded. For each target vertex in the support, most edges into the opposite target set are selected for multiplication. The thresholds for low degree are fractions of the degrees a , b a, b a , b guaranteed by cohesiveness.
Lemma 2.3 (Degree guesses for cohesive sets). For cohesive sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R , there are powers of two a , b ≥ 1 a, b \ge1 a , b ≥ 1 , depending only on S , T S,T S , T , such that e ( u , T ) ≥ a e(u,T) \ge a e ( u , T ) ≥ a for every u ∈ S u \in S u ∈ S , e ( S , w ) ≥ b e(S,w) \ge b e ( S , w ) ≥ b for every w ∈ T w \in T w ∈ T , and a b > d ( S , T ) / 4 \sqrt{ab} > d(S,T)/4 ab > d ( S , T ) /4 . For every k k k with ∣ S ∣ , ∣ T ∣ ≤ k |S|, |T| \le k ∣ S ∣ , ∣ T ∣ ≤ k , a , b ≤ k a,b \le k a , b ≤ k , a ∣ S ∣ ≤ 2 b k a|S| \le2bk a ∣ S ∣ ≤ 2 bk and b ∣ T ∣ ≤ 2 a k b|T| \le2ak b ∣ T ∣ ≤ 2 ak .
The proof is in Appendix § 7 .§ 1 . Since a , b a, b a , b depend on unknown S , T S,T S , T , the algorithm tries all pairs of powers of two in [ 1 , k ] [1,k] [ 1 , k ] .
For a step from L L L to R R R with U : = supp ( x ) U := \operatorname{supp}(x) U := supp ( x ) , the neighborhood graph of U U U is H : = ( U ∪ ˙ W , F ) H := (U \mathbin{\dot\cup} W,F) H := ( U ∪ ˙ W , F ) , where W : = N G ( U ) W := N_G(U) W := N G ( U ) is the set of neighbors of U U U and F F F is the set of edges incident to U U U . (For a step from R R R to L L L , we argue in the same way after exchanging a a a and b b b .) We seek a set F ′ ⊆ F F' \subseteq F F ′ ⊆ F of selected edges such that every w ∈ W w \in W w ∈ W is incident to at most b / 2 b/2 b /2 selected edges and every u ∈ U u \in U u ∈ U to at most a / 4 a/4 a /4 discarded edges. With each selected edge assigned weight 2 / b 2/b 2/ b , the weighted matrix has column-sum bound B ∞ = 1 B_\infty= 1 B ∞ = 1 . Each u ∈ S ∩ U u \in S \cap U u ∈ S ∩ U has at least a a a edges into T T T , of which at most a / 4 a/4 a /4 are discarded, so at least 3 a / 4 3a/4 3 a /4 of its edges into T T T belong to F ′ F' F ′ , regardless of its degree in G G G . Hence
∑ w ∈ T y ( w ) ≥ 3 a 2 b ∑ u ∈ S x ( u ) . (3) \sum_{w\in T} y(w) \ge\frac{3a}{2b}\sum_{u\in S} x(u). \tag*{(3)} w ∈ T ∑ y ( w ) ≥ 2 b 3 a u ∈ S ∑ x ( u ) . (3)
Here ∑ u ∈ S ∩ U x ( u ) = ∑ u ∈ S x ( u ) \sum_{u\in S\cap U} x(u) = \sum_{u\in S} x(u) ∑ u ∈ S ∩ U x ( u ) = ∑ u ∈ S x ( u ) since U = supp ( x ) U = \operatorname{supp}(x) U = supp ( x ) . Peel (Algorithm 1) selects edges by removing low-degree vertices, or returns dense subsets of the vertices it cannot remove.
If Peel removes every vertex, then an edge belongs to F ′ F' F ′ exactly when its endpoint in W W W is removed before its endpoint in U U U (line 5). Thus every w ∈ W w \in W w ∈ W has at most b / 2 b/2 b /2 selected edges and every u ∈ U u \in U u ∈ U at most a / 4 a/4 a /4 discarded edges, since these are its remaining edges when it is removed (line 2). If vertices remain, then every vertex of U ∗ U_* U ∗ has more than a / 4 a/4 a /4 neighbors in W ∗ W_* W ∗ and every vertex of W ∗ W_* W ∗ more than b / 2 b/2 b /2 neighbors in U ∗ U_* U ∗ (line 2), so that d H ( U ∗ , W ∗ ) > a b / 8 d_H(U_*,W_*) > \sqrt{ab}/8 d H ( U ∗ , W ∗ ) > ab /8 . In the search, ∣ U ∗ ∣ ≤ ∣ supp ( x ) ∣ |U_*| \le|\operatorname{supp}(x)| ∣ U ∗ ∣ ≤ ∣ supp ( x ) ∣ , and the support size is bounded by pruning as in (6), but ∣ W ∗ ∣ |W_*| ∣ W ∗ ∣ is not. To bound the output size, we replace W ∗ W_* W ∗ by a subset Y Y Y (line 9) with ∣ Y ∣ ≤ a ∣ U ∗ ∣ / ( 2 b ) + 1 |Y| \le a|U_*|/(2b)+1 ∣ Y ∣ ≤ a ∣ U ∗ ∣/ ( 2 b ) + 1 . Every vertex of Y Y Y still has more than b / 2 b/2 b /2 neighbors in U ∗ U_* U ∗ , and the density remains above a b / 8 \sqrt{ab}/8 ab /8 (see Lemma A.6(b)).
The algorithm and its guarantees
LocalDensep _p p (Algorithm 2) keeps the edge from v v v to its first neighbor as the first candidate, so that the output is nonempty with density at least one (lines 1 to 4). By guessing a , b a,b a , b among the Algorithm 1 Peel(H , x , a , b H,x,a,b H , x , a , b ): select edges or return subsets
Input: A bipartite graph H = ( U ∪ ˙ W , F ) H=(U\mathbin{\dot\cup}W,F) H = ( U ∪ ˙ W , F ) , a nonnegative vector x x x indexed by U U U , and a , b > 0 a,b>0 a , b > 0 .
Output: A nonnegative vector y y y indexed by W W W , or sets U ∗ , Y U_\ast,Y U ∗ , Y with ∅ ≠ U ∗ ⊆ U \varnothing\ne U_\ast\subseteq U ∅ = U ∗ ⊆ U and ∅ ≠ Y ⊆ W \varnothing\ne Y\subseteq W ∅ = Y ⊆ W .
U ∗ ← U , W ∗ ← W , F ′ ← ∅ U_\ast\leftarrow U,\quad W_\ast\leftarrow W,\quad F'\leftarrow\varnothing U ∗ ← U , W ∗ ← W , F ′ ← ∅
while there exists u ∈ U ∗ u\in U_\ast u ∈ U ∗ with e H ( u , W ∗ ) ≤ a / 4 e_H(u,W_\ast)\le a/4 e H ( u , W ∗ ) ≤ a /4 or w ∈ W ∗ w\in W_\ast w ∈ W ∗ with e H ( U ∗ , w ) ≤ b / 2 e_H(U_\ast,w)\le b/2 e H ( U ∗ , w ) ≤ b /2 do
Let q q q be the vertex with smallest identifier satisfying either condition.
if q ∈ W ∗ q\in W_\ast q ∈ W ∗ then
F ′ ← F ′ ∪ { u q ∈ F : u ∈ U ∗ } F'\leftarrow F'\cup\{uq\in F:u\in U_\ast\} F ′ ← F ′ ∪ { u q ∈ F : u ∈ U ∗ } and W ∗ ← W ∗ ∖ { q } W_\ast\leftarrow W_\ast\setminus\{q\} W ∗ ← W ∗ ∖ { q }
else
U ∗ ← U ∗ ∖ { q } U_\ast\leftarrow U_\ast\setminus\{q\} U ∗ ← U ∗ ∖ { q }
if U ∗ ∪ ˙ W ∗ = ∅ U_\ast\mathbin{\dot\cup}W_\ast=\varnothing U ∗ ∪ ˙ W ∗ = ∅ then return y y y indexed by W W W with y ( w ) : = 2 b ∑ u : u w ∈ F ′ x ( u ) y(w):=\frac{2}{b}\sum_{u:uw\in F'}x(u) y ( w ) := b 2 ∑ u : u w ∈ F ′ x ( u )
Let Y Y Y consist of the first min { ∣ W ∗ ∣ , a ∣ U ∗ ∣ 2 b } \min\{|W_\ast|,\frac{a|U_\ast|}{2b}\} min { ∣ W ∗ ∣ , 2 b a ∣ U ∗ ∣ } vertices of W ∗ W_\ast W ∗ in identifier order.
return ( U ∗ , Y ) (U_\ast,Y) ( U ∗ , Y )
powers of two in [ 1 , k ] [1,k] [ 1 , k ] (line 5), we lose only a constant factor in the approximation. To keep the computation local, Searchp _p p reads at most ⌈ σ 2 ⌉ \lceil\sigma^2\rceil ⌈ σ 2 ⌉ entries of each adjacency list and returns a star if it finds that many neighbors, since a star with that many leaves has density at least σ \sigma σ (line 14). It accepts the pruned vector as the next one only if it passes the weak-norm test of line 20, analyzed below.
For a starting vertex in L L L and a guess ( a , b ) (a,b) ( a , b ) , the search uses the density threshold σ \sigma σ , the pruning threshold δ \delta δ , and the weak-norm thresholds K t 1 / p K_t^{1/p} K t 1/ p , where
σ : = 3 a b 4 C p p / 2 , δ : = max { 1 , a / b } 4 k , K t : = { ( 3 / 4 ) t , t even , ( a / b ) ( 3 / 4 ) t , t odd . (4) \sigma:=\frac{\sqrt{3ab}}{4C_p^{p/2}},\qquad
\delta:=\frac{\max\{1,a/b\}}{4k},\qquad
K_t:=\begin{cases}
(3/4)^t, & t\text{ even},\\
(a/b)(3/4)^t, & t\text{ odd}.
\end{cases} \tag*{(4)} σ := 4 C p p /2 3 ab , δ := 4 k max { 1 , a / b } , K t := { ( 3/4 ) t , ( a / b ) ( 3/4 ) t , t even , t odd . (4)
The density threshold σ \sigma σ is a constant fraction of a b \sqrt{ab} ab , and σ < a b / 8 \sigma<\sqrt{ab}/8 σ < ab /8 since C p p > 2 C_p^p>2 C p p > 2 .
For a step from L L L to R R R , write x : = x t x:=x_t x := x t and y : = y t + 1 = ( 2 / b ) x A y:=y_{t+1}=(2/b)xA y := y t + 1 = ( 2/ b ) x A , where A A A is the adjacency matrix of the selected edges and has column-sum bound B ∞ = b / 2 B_\infty=b/2 B ∞ = b /2 (line 16). If d ( P i ( x ) , P m ( y ) ) ≤ σ d(P_i(x),P_m(y))\le\sigma d ( P i ( x ) , P m ( y )) ≤ σ for every prefix P i ( x ) P_i(x) P i ( x ) , then, using (2) , rescaling by 2 / b 2/b 2/ b , and substituting σ \sigma σ from (4) , we get
I y ( m ) ≤ ( 3 a 4 b ) 1 / p ∥ x ∥ p , ∞ m 1 − 1 / p . (5) I_y(m)\le\left(\frac{3a}{4b}\right)^{1/p}\lVert x\rVert_{p,\infty}m^{1-1/p}. \tag*{(5)} I y ( m ) ≤ ( 4 b 3 a ) 1/ p ∥ x ∥ p , ∞ m 1 − 1/ p . (5)
For δ > 0 \delta>0 δ > 0 and a nonnegative vector y y y , prune ( δ , y ) \operatorname{prune}(\delta,y) prune ( δ , y ) is obtained from y y y by setting every coordinate smaller than δ \delta δ to zero, and the pruned vector is z = prune ( δ , y t + 1 ) z=\operatorname{prune}(\delta,y_{t+1}) z = prune ( δ , y t + 1 ) (line 18). For every prefix P m ( z ) P_m(z) P m ( z ) , P m ( z ) = P m ( y t + 1 ) P_m(z)=P_m(y_{t+1}) P m ( z ) = P m ( y t + 1 ) and I z ( m ) = I y t + 1 ( m ) I_z(m)=I_{y_{t+1}}(m) I z ( m ) = I y t + 1 ( m ) , so (5) holds with z z z in place of y y y as well. Every positive coordinate of z z z is at least δ \delta δ , and the sum over any set Q Q Q decreases by at most δ ∣ Q ∣ \delta|Q| δ ∣ Q ∣ (Appendix A.2).
For cohesive sets S ⊆ L S\subseteq L S ⊆ L , T ⊆ R T\subseteq R T ⊆ R , a starting vertex v ∈ S v\in S v ∈ S , and the search with the guess ( a , b ) (a,b) ( a , b ) from Lemma 2.3 , we consider the mass on the target side, multiplied by b / a b/a b / a when that side is T T T . Whenever Peel returns a vector, its weighted target mass before pruning is at least 3 / 2 3/2 3/2 times the previous value, by (3) . By Lemma 2.3 , the bounds ∣ S ∣ , ∣ T ∣ ≤ k |S|,|T|\le k ∣ S ∣ , ∣ T ∣ ≤ k , and the choice of δ \delta δ in (4) ,
∣ S ∣ ≤ min { k , 2 b k / a } ≤ 1 2 δ , ( b / a ) ∣ T ∣ ≤ min { ( b / a ) k , 2 k } ≤ 1 2 δ . |S|\le\min\{k,2bk/a\}\le\frac{1}{2\delta},\qquad
(b/a)|T|\le\min\{(b/a)k,2k\}\le\frac{1}{2\delta}. ∣ S ∣ ≤ min { k , 2 bk / a } ≤ 2 δ 1 , ( b / a ) ∣ T ∣ ≤ min {( b / a ) k , 2 k } ≤ 2 δ 1 .
Thus at most max { δ ∣ S ∣ , ( b / a ) δ ∣ T ∣ } ≤ 1 / 2 \max\{\delta|S|,(b/a)\delta|T|\}\le1/2 max { δ ∣ S ∣ , ( b / a ) δ ∣ T ∣ } ≤ 1/2 is lost during pruning. The initial weighted target mass is one, so by induction it remains at least one after every pruning step in the search with guess ( a , b ) (a,b) ( a , b ) . In particular, z ≠ 0 z\ne0 z = 0 at each such step.
The search accepts z z z as the next vector only if ∥ z ∥ p , ∞ ≤ K t + 1 1 / p \lVert z\rVert_{p,\infty}\le K_{t+1}^{1/p} ∥ z ∥ p , ∞ ≤ K t + 1 1/ p , so every x t x_t x t satisfies ∥ x t ∥ p , ∞ ≤ K t 1 / p \lVert x_t\rVert_{p,\infty}\le K_t^{1/p} ∥ x t ∥ p , ∞ ≤ K t 1/ p (lines 20 and 21). The thresholds are chosen to match (5) : starting from K 0 = 1 K_0=1 K 0 = 1 , K t 1 / p K_t^{1/p} K t 1/ p is
Algorithm 2 Local approximation, for p > 2 p > 2 p > 2
LocalDensep ( G , v , k ) _p(G, v, k) p ( G , v , k )
Input: Neighbor-query access to G = ( L ∪ ˙ R , E ) G = (L \mathbin{\dot\cup} R, E) G = ( L ∪ ˙ R , E ) , a vertex v ∈ L ∪ ˙ R v \in L \mathbin{\dot\cup} R v ∈ L ∪ ˙ R , and an integer k ≥ 1 k \ge1 k ≥ 1 .
Output: Nonempty X ⊆ L X \subseteq L X ⊆ L , Y ⊆ R Y \subseteq R Y ⊆ R , or ⊥ \bot ⊥ if v v v is isolated.
Query the first neighbor u u u of v v v .
if u = ⊥ u = \bot u = ⊥ then return ⊥ \bot ⊥
if v ∈ R v \in R v ∈ R then exchange the roles of L L L and R R R below, and swap the returned sets
C ← { ( { v } , { u } ) } C \leftarrow\{(\{v\}, \{u\})\} C ← {({ v } , { u })}
for each a , b ∈ { 2 0 , 2 1 , … , 2 ⌊ log 2 k ⌋ } a,b \in\{2^0,2^1,\ldots,2^{\lfloor\log_2 k\rfloor}\} a , b ∈ { 2 0 , 2 1 , … , 2 ⌊ l o g 2 k ⌋ } do
r ← Search p ( G , v , k , a , b ) r \leftarrow\operatorname{Search}_p(G,v,k,a,b) r ← Search p ( G , v , k , a , b )
if r ≠ ⊥ r \ne\bot r = ⊥ then add r r r (ordered with its current L L L -subset first) to C C C
return ( X , Y ) ∈ C (X,Y) \in C ( X , Y ) ∈ C maximizing d ( X , Y ) d(X,Y) d ( X , Y )
Searchp ( G , v , k , a , b ) _p(G,v,k,a,b) p ( G , v , k , a , b )
Input: The inputs above, with v ∈ L v \in L v ∈ L , and a guess a , b ∈ [ 1 , k ] a,b \in[1,k] a , b ∈ [ 1 , k ] .
Output: Two nonempty vertex sets on opposite sides of G G G , or ⊥ \bot ⊥ .
Take σ , δ , ( K t ) t ≥ 0 \sigma,\delta,(K_t)_{t\ge0} σ , δ , ( K t ) t ≥ 0 from (4), and set x 0 ← 1 v x_0 \leftarrow1_v x 0 ← 1 v .
for t = 0 , 1 , 2 , … t=0,1,2,\ldots t = 0 , 1 , 2 , … do
( a t , b t ) ← ( a , b ) (a_t,b_t) \leftarrow(a,b) ( a t , b t ) ← ( a , b ) if t t t is even, and ( b , a ) (b,a) ( b , a ) if t t t is odd
for each u ∈ supp ( x t ) u \in\operatorname{supp}(x_t) u ∈ supp ( x t ) do
Read the adjacency list of u u u , stopping after ⌈ σ 2 ⌉ \lceil\sigma^2\rceil ⌈ σ 2 ⌉ entries, and let N u N_u N u be the set of neighbors read.
if ∣ N u ∣ = ⌈ σ 2 ⌉ |N_u|=\lceil\sigma^2\rceil ∣ N u ∣ = ⌈ σ 2 ⌉ then return ( { u } , N u ) (\{u\},N_u) ({ u } , N u )
Let H : = ( supp ( x t ) ∪ ˙ W , F ) H := (\operatorname{supp}(x_t) \mathbin{\dot\cup} W,F) H := ( supp ( x t ) ∪ ˙ W , F ) be the neighborhood graph of supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) , with W : = N G ( supp ( x t ) ) W := N_G(\operatorname{supp}(x_t)) W := N G ( supp ( x t )) .
r ← Peel ( H , x t , a t , b t ) r \leftarrow\operatorname{Peel}(H,x_t,a_t,b_t) r ← Peel ( H , x t , a t , b t )
if r r r consists of sets U ∗ , Y U_*,Y U ∗ , Y then return ( U ∗ , Y ) (U_*,Y) ( U ∗ , Y )
y t + 1 ← r , z ← prune ( δ , y t + 1 ) y_{t+1} \leftarrow r,\ z \leftarrow\operatorname{prune}(\delta,y_{t+1}) y t + 1 ← r , z ← prune ( δ , y t + 1 )
if z = 0 z=0 z = 0 then return ⊥ \bot ⊥
if ∥ z ∥ p , ∞ ≤ K t + 1 1 / p \lVert z\rVert_{p,\infty} \le K_{t+1}^{1/p} ∥ z ∥ p , ∞ ≤ K t + 1 1/ p then
x t + 1 ← z x_{t+1} \leftarrow z x t + 1 ← z
else
Let m ≥ 1 m \ge1 m ≥ 1 be the smallest index such that I z ( m ) > K t + 1 1 / p m 1 − 1 / p I_z(m) > K_{t+1}^{1/p}m^{1-1/p} I z ( m ) > K t + 1 1/ p m 1 − 1/ p .
return ( P i ( x t ) , P m ( z ) ) (P_i(x_t),P_m(z)) ( P i ( x t ) , P m ( z )) for the smallest i i i with d H ( P i ( x t ) , P m ( z ) ) > σ d_H(P_i(x_t),P_m(z))>\sigma d H ( P i ( x t ) , P m ( z )) > σ , or ⊥ \bot ⊥ if none exists
multiplied by ( 3 a / ( 4 b ) ) 1 / p (3a/(4b))^{1/p} ( 3 a / ( 4 b ) ) 1/ p in each step from L L L to R R R and by ( 3 b / ( 4 a ) ) 1 / p (3b/(4a))^{1/p} ( 3 b / ( 4 a ) ) 1/ p in each step from R R R to $L, as specified for K t K_t K t in (4). Hence, if d ( P i ( x t ) , P m ( z ) ) ≤ σ d(P_i(x_t),P_m(z)) \le\sigma d ( P i ( x t ) , P m ( z )) ≤ σ for all prefixes P i ( x t ) , P m ( z ) P_i(x_t),P_m(z) P i ( x t ) , P m ( z ) , then, by (5) and ∥ x t ∥ p , ∞ ≤ K t 1 / p \lVert x_t\rVert_{p,\infty} \le K_t^{1/p} ∥ x t ∥ p , ∞ ≤ K t 1/ p , I z ( m ) ≤ K t + 1 1 / p m 1 − 1 / p I_z(m) \le K_{t+1}^{1/p}m^{1-1/p} I z ( m ) ≤ K t + 1 1/ p m 1 − 1/ p for every integer $1 \le m \le |\operatorname{supp}(z)|$. By Lemma A.3 (a), the supremum defining ∥ z ∥ p , ∞ \lVert z\rVert_{p,\infty} ∥ z ∥ p , ∞ is attained at such an integer, so z z z passes the test. Over two steps, the threshold decreases by a factor of ( 3 / 4 ) 2 / p (3/4)^{2/p} ( 3/4 ) 2/ p . If z z z fails the test, Search p \operatorname{Search}_p Search p finds the shortest prefix P m ( z ) P_m(z) P m ( z ) whose sum exceeds K t + 1 1 / p m 1 − 1 / p K_{t+1}^{1/p}m^{1-1/p} K t + 1 1/ p m 1 − 1/ p (line 23). Since the bound (5) fails for this prefix, some prefix P i ( x t ) P_i(x_t) P i ( x t ) has d ( P i ( x t ) , P m ( z ) ) > σ d(P_i(x_t),P_m(z))>\sigma d ( P i ( x t ) , P m ( z )) > σ , and the search returns these two prefixes (line 24).
Output size and locality. Every positive coordinate of x t x_t x t is at least δ \delta δ and ∥ x t ∥ p , ∞ ≤ K t 1 / p \lVert x_t\rVert_{p,\infty} \le K_t^{1/p} ∥ x t ∥ p , ∞ ≤ K t 1/ p , so, by the choice of parameters in (4),
∣ supp ( x t ) ∣ ≤ K t δ − p ≤ ( 4 k ) p ( 3 / 4 ) t , ∑ t ∣ supp ( x t ) ∣ ≤ 4 ( 4 k ) p . (6) |\operatorname{supp}(x_t)| \le K_t\delta^{-p} \le(4k)^p(3/4)^t,\qquad\sum_t|\operatorname{supp}(x_t)| \le4(4k)^p. \tag*{(6)} ∣ supp ( x t ) ∣ ≤ K t δ − p ≤ ( 4 k ) p ( 3/4 ) t , t ∑ ∣ supp ( x t ) ∣ ≤ 4 ( 4 k ) p . (6)
and each set returned by a sweep or by peeling has at most ( 4 k ) p (4k)^p ( 4 k ) p vertices (Lemma B.1 (d)), so the output has O p ( k p ) O_p(k^p) O p ( k p ) vertices. Every vertex of supp ( x t + 1 ) \operatorname{supp}(x_{t+1}) supp ( x t + 1 ) has a neighbor in supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) , so the sets returned at step t t t lie within distance t + 1 t+1 t + 1 of v v v , where t ≤ p log 4 / 3 ( 4 k ) t \le p\log_{4/3}(4k) t ≤ p log 4/3 ( 4 k ) by (6). In particular, for p = 2 + ϵ p=2+\epsilon p = 2 + ϵ , every returned vertex lies within distance O ϵ ( log 2 ( 2 k ) ) O_\epsilon(\log_2(2k)) O ϵ ( log 2 ( 2 k )) of v v v (Lemma B.3 ).
The algorithm makes O p ( k p min { ( Δ + 1 ) log 2 2 ( 2 k ) , k 2 } ) O_p\left(k^p\min\left\{(\Delta+1)\log_2^2(2k),k^2\right\}\right) O p ( k p min { ( Δ + 1 ) log 2 2 ( 2 k ) , k 2 } ) neighbor queries (Appendix B.2).
Constant approximation. We prove that, for every p > 2 p>2 p > 2 and S , T , k , v S,T,k,v S , T , k , v as in Theorem 1.2 , the output ( X , Y ) (X,Y) ( X , Y ) of LocalDense p ( G , v , k ) \operatorname{LocalDense}_p(G,v,k) LocalDense p ( G , v , k ) satisfies
d ( X , Y ) > 3 16 C p − p / 2 d ( S , T ) . (7) d(X,Y)>\frac{\sqrt{3}}{16}C_p^{-p/2}d(S,T). \tag*{(7)} d ( X , Y ) > 16 3 C p − p /2 d ( S , T ) . (7)
We choose ( a , b ) (a,b) ( a , b ) as in Lemma 2.3 and suppose first that v ∈ S v\in S v ∈ S . By the induction above, z ≠ 0 z\ne0 z = 0 at every pruning step in the search with guess ( a , b ) (a,b) ( a , b ) . The search cannot continue indefinitely, since 1 ≤ ∑ u ∈ S x t ( u ) ≤ ( 3 / 4 ) t / p k 1 − 1 / p 1\le\sum_{u\in S}x_t(u)\le(3/4)^{t/p}k^{1-1/p} 1 ≤ ∑ u ∈ S x t ( u ) ≤ ( 3/4 ) t / p k 1 − 1/ p at every even step. Thus Search p \operatorname{Search}_p Search p returns sets of density at least σ \sigma σ within O p ( log 2 ( 2 k ) ) O_p(\log_2(2k)) O p ( log 2 ( 2 k )) steps. Since a b > d ( S , T ) / 4 \sqrt{ab}>d(S,T)/4 ab > d ( S , T ) /4 , their density satisfies (7). For v ∈ T v\in T v ∈ T , we exchange L , R L,R L , R and a , b a,b a , b . All other searches also terminate by (6), and LocalDense p \operatorname{LocalDense}_p LocalDense p returns the densest candidate. For ϵ > 0 \epsilon>0 ϵ > 0 and p : = 2 + ϵ p:=2+\epsilon p := 2 + ϵ , we obtain the guarantees of Theorem 1.2 , with approximation ratio O ( 1 + 1 / ϵ ) O(1+1/\epsilon) O ( 1 + 1/ ϵ ) , by direct calculation from (6) and (7), using C p − p / 2 ≥ ϵ / ( e ( 1 + ϵ ) ) C_p^{-p/2}\ge\epsilon/(\sqrt{e}(1+\epsilon)) C p − p /2 ≥ ϵ / ( e ( 1 + ϵ )) ; see Appendix § 8 .§ 3 for details.
Limitations on improving the output size
For a target with at most k k k vertices per side, our algorithm returns O ϵ ( k 2 + ϵ ) O_\epsilon(k^{2+\epsilon}) O ϵ ( k 2 + ϵ ) vertices with a constant approximation ratio. Can the output be reduced to O ( k ) O(k) O ( k ) or o ( k 2 ) o(k^2) o ( k 2 ) while keeping the approximation ratio constant? The threshold k 2 k^2 k 2 appears because we ask for approximation rather than recovery: a star with k 2 k^2 k 2 leaves has density k k k and is as dense as any target with at most k k k vertices per side, whereas a star with o ( k 2 ) o(k^2) o ( k 2 ) leaves has density o ( k ) o(k) o ( k ) . We rule out output size ϕ ( k ) = o ( k 2 ) \phi(k)=o(k^2) ϕ ( k ) = o ( k 2 ) per side in two settings:
Restricted queries. If the worst-case number of queries is bounded by a function of k k k alone, or more generally is o ( Δ ) o(\Delta) o ( Δ ) for every fixed k k k , while computation between queries is unrestricted, then, on some instance and from every target vertex, even a randomized algorithm fails with probability at least 2 / 3 2/3 2/3 to return a constant approximation. We choose k k k centers per side uniformly among many disjoint stars and place the edges of a complete bipartite subgraph at uniformly chosen adjacency-list positions. We compare runs before and after this modification using the same algorithmic randomness. Unless the algorithm receives different answers or includes a target center other than the starting vertex in its output, any returned sets have density at most 2 ϕ ( k ) = o ( k ) \sqrt{2\phi(k)}=o(k) 2 ϕ ( k ) = o ( k ) , whereas the target has density k k k . By summing the success probabilities over target vertices and averaging over the random construction, we obtain one graph on which the algorithm fails with probability at least 2 / 3 2/3 2/3 from every target vertex. The formal statement is Theorem D.2 , proved in Appendix § 10 .§ 1 .
Restricted running time. If the algorithm may read the entire graph but must run in time f ( k ) ∣ V ∣ O ( 1 ) f(k)|V|^{O(1)} f ( k ) ∣ V ∣ O ( 1 ) for a computable function f f f of k k k , the limitation is that we need to find not only a dense subgraph, but also a small one. For a graph J J J promised to contain a k k k -clique, the two copies S , T S,T S , T of the clique in its bipartite double cover have d ( S , T ) = k − 1 d(S,T)=k-1 d ( S , T ) = k − 1 . From returned sets X , Y X,Y X , Y with d ( X , Y ) = Ω ( k ) d(X,Y)=\Omega(k) d ( X , Y ) = Ω ( k ) and ∣ X ∣ , ∣ Y ∣ ≤ ϕ ( k ) |X|,|Y|\le\phi(k) ∣ X ∣ , ∣ Y ∣ ≤ ϕ ( k ) , we extract a set U U U of k k k vertices of J J J spanning Ω ( k 3 / ( k + ϕ ( k ) ) ) \Omega(k^3/(k+\phi(k))) Ω ( k 3 / ( k + ϕ ( k ))) edges. Since the optimal k k k -vertex subgraph has ( k 2 ) \binom{k}{2} ( 2 k ) edges, the approximation ratio for Densest k k k -Subgraph would be O ( 1 + ϕ ( k ) / k ) = o ( k ) O(1+\phi(k)/k)=o(k) O ( 1 + ϕ ( k ) / k ) = o ( k ) , which under the Strongish Planted Clique Hypothesis (SPCH) of Manurangsi et al. [30 ] is impossible in this running time, even with randomization. The formal statement is Theorem D.8 , proved in Appendix § 10 .§ 2.2 . Under ETH, we obtain a weaker output-size bound by the same reduction (Theorem D.12 , proved in Appendix § 10 .§ 2.3 ).
Conclusion
We give the first constant-factor local approximation algorithm for the bipartite densest subgraph problem, with output size, number of queries, and running time depending on k k k alone (Theorem 1.2 ). Like the density itself, the guarantee does not depend on edges outside the subgraph induced by S ∪ ˙ T S \mathbin{\dot\cup} T S ∪ ˙ T .
The main technical question left unanswered is the following: while sub -quadratic output is impossible in the settings of § 3 , quadratic output is not ruled out, and we leave open whether it is possible to achieve a constant-factor approximation with output of size O ( k 2 ) O(k^2) O ( k 2 ) .
Beyond improving the output size and approximation ratio, is it possible, under suitable assumptions, to ensure that the returned sets overlap with the target sets? Such results are known in the case of conductance, i.e., the classical application of the Lovász–Simonovits curve—see, for example, [37 , 5 ] .
Acknowledgements
Guy Weissenberg was supported by the Swiss National Science Foundation grant 10004935 - Sublinear Algorithms for Non-linear Structures (Project MINT).
AI use statement
In this work, we used generative AI tools for brainstorming, writing and editing. We have reviewed all AI-assisted work, and constructed the main arguments in the paper ourselves. We checked the LLM-generated ideas for potential plagiarism through a manual literature survey. We take responsibility for the final content of this work, including its presentation, text, claims and proofs.
Technical lemmas for the local algorithm
We prove the statements deferred from Sections 1 and 2.
Cohesive subsets and degree guesses
Lemma A.1 (Existence of cohesive subsets). For all sets S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R with e ( S , T ) > 0 e(S,T) > 0 e ( S , T ) > 0 , there are cohesive subsets S ∗ ⊆ S S^{*} \subseteq S S ∗ ⊆ S and T ∗ ⊆ T T^{*} \subseteq T T ∗ ⊆ T satisfying d ( S ∗ , T ∗ ) ≥ d ( S , T ) d(S^{*},T^{*}) \ge d(S,T) d ( S ∗ , T ∗ ) ≥ d ( S , T ) .
Proof. Choose nonempty sets S ∗ ⊆ S S^* \subseteq S S ∗ ⊆ S and T ∗ ⊆ T T^* \subseteq T T ∗ ⊆ T maximizing d ( S ∗ , T ∗ ) d(S^*, T^*) d ( S ∗ , T ∗ ) . Then d ( S ∗ , T ∗ ) ≥ d ( S , T ) > 0 d(S^*, T^*) \ge d(S,T) > 0 d ( S ∗ , T ∗ ) ≥ d ( S , T ) > 0 . For u ∈ S ∗ u \in S^* u ∈ S ∗ , the bound e ( u , T ∗ ) ≥ e ( S ∗ , T ∗ ) / ( 2 ∣ S ∗ ∣ ) e(u,T^*) \ge e(S^*,T^*)/(2|S^*|) e ( u , T ∗ ) ≥ e ( S ∗ , T ∗ ) / ( 2∣ S ∗ ∣ ) is trivial if S ∗ = { u } S^*=\{u\} S ∗ = { u } . Otherwise, by maximality, d ( S ∗ ∖ { u } , T ∗ ) ≤ d ( S ∗ , T ∗ ) d(S^* \setminus\{u\},T^*) \le d(S^*,T^*) d ( S ∗ ∖ { u } , T ∗ ) ≤ d ( S ∗ , T ∗ ) , that is,
e ( S ∗ , T ∗ ) − e ( u , T ∗ ) ( ∣ S ∗ ∣ − 1 ) ∣ T ∗ ∣ ≤ e ( S ∗ , T ∗ ) ∣ S ∗ ∣ ∣ T ∗ ∣ . \frac{e(S^*,T^*)-e(u,T^*)}{\sqrt{(|S^*|-1)|T^*|}} \le\frac{e(S^*,T^*)}{\sqrt{|S^*||T^*|}}. ( ∣ S ∗ ∣ − 1 ) ∣ T ∗ ∣ e ( S ∗ , T ∗ ) − e ( u , T ∗ ) ≤ ∣ S ∗ ∣∣ T ∗ ∣ e ( S ∗ , T ∗ ) .
Rearranging and using 1 − t ≤ 1 − t / 2 \sqrt{1-t} \le1-t/2 1 − t ≤ 1 − t /2 , we get
1 − e ( u , T ∗ ) e ( S ∗ , T ∗ ) ≤ 1 − 1 ∣ S ∗ ∣ ≤ 1 − 1 2 ∣ S ∗ ∣ , 1-\frac{e(u,T^*)}{e(S^*,T^*)} \le\sqrt{1-\frac{1}{|S^*|}} \le1-\frac{1}{2|S^*|}, 1 − e ( S ∗ , T ∗ ) e ( u , T ∗ ) ≤ 1 − ∣ S ∗ ∣ 1 ≤ 1 − 2∣ S ∗ ∣ 1 ,
so e ( u , T ∗ ) ≥ e ( S ∗ , T ∗ ) / ( 2 ∣ S ∗ ∣ ) e(u,T^*) \ge e(S^*,T^*)/(2|S^*|) e ( u , T ∗ ) ≥ e ( S ∗ , T ∗ ) / ( 2∣ S ∗ ∣ ) . By symmetry, e ( S ∗ , w ) ≥ e ( S ∗ , T ∗ ) / ( 2 ∣ T ∗ ∣ ) e(S^*,w) \ge e(S^*,T^*)/(2|T^*|) e ( S ∗ , w ) ≥ e ( S ∗ , T ∗ ) / ( 2∣ T ∗ ∣ ) for every w ∈ T ∗ w \in T^* w ∈ T ∗ , so S ∗ , T ∗ S^*,T^* S ∗ , T ∗ are cohesive.
Proof of Lemma 2.3. Let a 0 : = e ( S , T ) / ( 2 ∣ S ∣ ) a_0 := e(S,T)/(2|S|) a 0 := e ( S , T ) / ( 2∣ S ∣ ) and b 0 : = e ( S , T ) / ( 2 ∣ T ∣ ) b_0 := e(S,T)/(2|T|) b 0 := e ( S , T ) / ( 2∣ T ∣ ) . Since S , T S,T S , T are cohesive, e ( u , T ) ≥ a 0 e(u,T) \ge a_0 e ( u , T ) ≥ a 0 for every u ∈ S u \in S u ∈ S and e ( S , w ) ≥ b 0 e(S,w) \ge b_0 e ( S , w ) ≥ b 0 for every w ∈ T w \in T w ∈ T . The guesses a a a and b b b are the largest powers of two not exceeding max ( a 0 , 1 ) \max(a_0,1) max ( a 0 , 1 ) and max ( b 0 , 1 ) \max(b_0,1) max ( b 0 , 1 ) , respectively, so that
a 0 < 2 a , b 0 < 2 b . (8) a_0 < 2a,\qquad b_0 < 2b. \tag*{(8)} a 0 < 2 a , b 0 < 2 b . (8)
Degrees are integers and a 0 , b 0 > 0 a_0,b_0>0 a 0 , b 0 > 0 , so e ( u , T ) ≥ max ( a 0 , 1 ) ≥ a e(u,T) \ge\max(a_0,1) \ge a e ( u , T ) ≥ max ( a 0 , 1 ) ≥ a for every u ∈ S u \in S u ∈ S , and similarly e ( S , w ) ≥ b e(S,w) \ge b e ( S , w ) ≥ b for every w ∈ T w \in T w ∈ T . By (8),
a b > a 0 b 0 2 = d ( S , T ) 4 . \sqrt{ab} > \frac{\sqrt{a_0b_0}}{2} = \frac{d(S,T)}{4}. ab > 2 a 0 b 0 = 4 d ( S , T ) .
For any k k k with ∣ S ∣ , ∣ T ∣ ≤ k |S|,|T| \le k ∣ S ∣ , ∣ T ∣ ≤ k , a 0 , b 0 ≤ k / 2 a_0,b_0 \le k/2 a 0 , b 0 ≤ k /2 and hence a , b ≤ k a,b \le k a , b ≤ k . It remains to show a ∣ S ∣ ≤ 2 b k a|S| \le2bk a ∣ S ∣ ≤ 2 bk , as b ∣ T ∣ ≤ 2 a k b|T| \le2ak b ∣ T ∣ ≤ 2 ak follows by symmetry. If a = 1 a=1 a = 1 , then a ∣ S ∣ = ∣ S ∣ ≤ k ≤ 2 b k a|S|=|S| \le k \le2bk a ∣ S ∣ = ∣ S ∣ ≤ k ≤ 2 bk . If a > 1 a>1 a > 1 , then a ≤ a 0 a \le a_0 a ≤ a 0 and
a ∣ S ∣ ≤ a 0 ∣ S ∣ = b 0 ∣ T ∣ < 2 b ∣ T ∣ ≤ 2 b k . a|S| \le a_0|S| = b_0|T| < 2b|T| \le2bk. a ∣ S ∣ ≤ a 0 ∣ S ∣ = b 0 ∣ T ∣ < 2 b ∣ T ∣ ≤ 2 bk .
Corollary A.2 (Arbitrary target sets). For every ϵ > 0 \epsilon> 0 ϵ > 0 and all sets S ⊆ L S \subseteq L S ⊆ L , T ⊆ R T \subseteq R T ⊆ R with e ( S , T ) > 0 e(S,T)>0 e ( S , T ) > 0 and ∣ S ∣ , ∣ T ∣ ≤ k |S|,|T| \le k ∣ S ∣ , ∣ T ∣ ≤ k , there are S ′ ⊆ S S' \subseteq S S ′ ⊆ S and T ′ ⊆ T T' \subseteq T T ′ ⊆ T with e ( S ′ , T ′ ) ≥ e ( S , T ) / 2 e(S',T') \ge e(S,T)/2 e ( S ′ , T ′ ) ≥ e ( S , T ) /2 such that, from every starting vertex v ∈ S ′ ∪ ˙ T ′ v \in S' \mathbin{\dot\cup} T' v ∈ S ′ ∪ ˙ T ′ , the algorithm LocalDense 2 + ϵ ( G , v , k ) \operatorname{LocalDense}_{2+\epsilon}(G,v,k) LocalDense 2 + ϵ ( G , v , k ) satisfies (i) of Theorem 1.2 and its output ( X , Y ) (X,Y) ( X , Y ) satisfies d ( X , Y ) ≥ 3 32 e ϵ 1 + ϵ d ( S , T ) d(X,Y) \ge\frac{\sqrt{3}}{32\sqrt{e}}\frac{\epsilon}{1+\epsilon}d(S,T) d ( X , Y ) ≥ 32 e 3 1 + ϵ ϵ d ( S , T ) .
Proof. By Lemma C.2, there are S ′ ⊆ S S' \subseteq S S ′ ⊆ S and T ′ ⊆ T T' \subseteq T T ′ ⊆ T with e ( S ′ , T ′ ) ≥ e ( S , T ) / 2 e(S',T') \ge e(S,T)/2 e ( S ′ , T ′ ) ≥ e ( S , T ) /2 such that e ( u , T ′ ) > a 0 e(u,T') > a_0 e ( u , T ′ ) > a 0 for every u ∈ S ′ u \in S' u ∈ S ′ and e ( S ′ , w ) > b 0 e(S',w) > b_0 e ( S ′ , w ) > b 0 for every w ∈ T ′ w \in T' w ∈ T ′ , where now a 0 : = e ( S , T ) / ( 4 ∣ S ∣ ) a_0 := e(S,T)/(4|S|) a 0 := e ( S , T ) / ( 4∣ S ∣ ) and b 0 : = e ( S , T ) / ( 4 ∣ T ∣ ) b_0 := e(S,T)/(4|T|) b 0 := e ( S , T ) / ( 4∣ T ∣ ) . Since e ( S , T ) ≤ ∣ S ∣ ∣ T ∣ e(S,T) \le|S||T| e ( S , T ) ≤ ∣ S ∣∣ T ∣ , both a 0 a_0 a 0 and b 0 b_0 b 0 are at most k / 4 k/4 k /4 . Rounding as in the proof of Lemma 2.3, we choose powers of two a , b ≤ k a,b \le k a , b ≤ k with e ( u , T ′ ) ≥ a e(u,T') \ge a e ( u , T ′ ) ≥ a for every u ∈ S ′ u \in S' u ∈ S ′ , e ( S ′ , w ) ≥ b e(S',w) \ge b e ( S ′ , w ) ≥ b for every w ∈ T ′ w \in T' w ∈ T ′ , and a b > a 0 b 0 / 2 = d ( S , T ) / 8 \sqrt{ab} > \sqrt{a_0b_0}/2 = d(S,T)/8 ab > a 0 b 0 /2 = d ( S , T ) /8 .
If a > 1 a>1 a > 1 , then a ∣ S ′ ∣ ≤ a 0 ∣ S ∣ = b 0 ∣ T ∣ < 2 b ∣ T ∣ ≤ 2 b k a|S'| \le a_0|S| = b_0|T| < 2b|T| \le2bk a ∣ S ′ ∣ ≤ a 0 ∣ S ∣ = b 0 ∣ T ∣ < 2 b ∣ T ∣ ≤ 2 bk , and if a = 1 a=1 a = 1 , then a ∣ S ′ ∣ ≤ k ≤ 2 b k a|S'| \le k \le2bk a ∣ S ′ ∣ ≤ k ≤ 2 bk . By symmetry, b ∣ T ′ ∣ ≤ 2 a k b|T'| \le2ak b ∣ T ′ ∣ ≤ 2 ak .
In the proof of (7) in § 2.3 , we use only these properties of the target sets and of the guess ( a , b ) (a,b) ( a , b ) , so from every v ∈ S ′ ∪ ˙ T ′ v \in S' \mathbin{\dot\cup} T' v ∈ S ′ ∪ ˙ T ′ the output has density above 3 32 C p − p / 2 d ( S , T ) \frac{\sqrt{3}}{32}C_p^{-p/2}d(S,T) 32 3 C p − p /2 d ( S , T ) . By (17), d ( X , Y ) > 3 32 e ϵ 1 + ϵ d ( S , T ) d(X,Y) > \frac{\sqrt{3}}{32\sqrt{e}}\frac{\epsilon}{1+\epsilon}d(S,T) d ( X , Y ) > 32 e 3 1 + ϵ ϵ d ( S , T ) . The bounds in (i) hold for every starting vertex by Theorem B.2 .
Weak-ℓ p \ell_p ℓ p preliminaries and pruning
Lemma A.3 (Prefix sums, support size, and pruning). For a nonzero vector x ≥ 0 x \ge0 x ≥ 0 with ℓ : = ∣ supp ( x ) ∣ \ell:= |\operatorname{supp}(x)| ℓ := ∣ supp ( x ) ∣ , p ≥ 2 p \ge2 p ≥ 2 and δ > 0 \delta> 0 δ > 0 :
(a) The supremum in the definition of ∥ x ∥ p , ∞ \|x\|_{p,\infty} ∥ x ∥ p , ∞ is attained at an integer m ≤ ℓ m \le\ell m ≤ ℓ , that is,
∥ x ∥ p , ∞ = max 1 ≤ m ≤ ℓ I x ( m ) m 1 − 1 / p . (9) \|x\|_{p,\infty} = \max_{1 \le m \le\ell} \frac{I_x(m)}{m^{1-1/p}}. \tag*{(9)} ∥ x ∥ p , ∞ = 1 ≤ m ≤ ℓ max m 1 − 1/ p I x ( m ) . (9) (b) If every positive coordinate of x x x is at least δ \delta δ , then ℓ ≤ ∥ x ∥ p , ∞ p / δ p \ell\le\|x\|_{p,\infty}^{p}/\delta^{p} ℓ ≤ ∥ x ∥ p , ∞ p / δ p .
(c) For y ≥ 0 y \ge0 y ≥ 0 and z : = prune ( δ , y ) z := \operatorname{prune}(\delta,y) z := prune ( δ , y ) , z ≤ y z \le y z ≤ y , every positive coordinate of z z z is at least δ \delta δ , and
0 ≤ ∑ w ∈ Q ( y ( w ) − z ( w ) ) ≤ δ ∣ Q ∣ ( Q ⊆ V ) . (10) 0 \le\sum_{w \in Q} (y(w)-z(w)) \le\delta|Q| \qquad(Q \subseteq V). \tag*{(10)} 0 ≤ w ∈ Q ∑ ( y ( w ) − z ( w )) ≤ δ ∣ Q ∣ ( Q ⊆ V ) . (10)
Proof of Lemma A.3. We prove each item below.
(a) On ( 0 , 1 ] (0,1] ( 0 , 1 ] the ratio I x ( s ) / s 1 − 1 / p = x ( 1 ) s 1 / p I_x(s)/s^{1-1/p}=x_{(1)}s^{1/p} I x ( s ) / s 1 − 1/ p = x ( 1 ) s 1/ p increases, and for s > ℓ s>\ell s > ℓ the numerator is constant while the denominator increases. On each interval [ i − 1 , i ] [i-1,i] [ i − 1 , i ] with 2 ≤ i ≤ ℓ 2 \le i \le\ell 2 ≤ i ≤ ℓ , I x I_x I x is linear (Definition 2.1) and s 1 − 1 / p s^{1-1/p} s 1 − 1/ p is concave. With c c c the maximum of the ratio over this interval, I x ( s ) − c s 1 − 1 / p I_x(s)-cs^{1-1/p} I x ( s ) − c s 1 − 1/ p is convex with maximum zero, and a convex function attains its maximum at an endpoint of the interval, so the ratio equals c c c at an endpoint. Hence the supremum is attained at an integer m ≤ ℓ m \le\ell m ≤ ℓ .
(b) Every positive coordinate is at least δ \delta δ , so ℓ δ ≤ I x ( ℓ ) ≤ ∥ x ∥ p , ∞ ℓ 1 − 1 / p \ell\delta\le I_x(\ell) \le\|x\|_{p,\infty}\ell^{1-1/p} ℓ δ ≤ I x ( ℓ ) ≤ ∥ x ∥ p , ∞ ℓ 1 − 1/ p by Definition 2.1, and hence ℓ ≤ ∥ x ∥ p , ∞ p / δ p \ell\le\|x\|_{p,\infty}^{p}/\delta^{p} ℓ ≤ ∥ x ∥ p , ∞ p / δ p .
(c) Each coordinate of y − z y-z y − z lies in [ 0 , δ ) [0,\delta) [ 0 , δ ) .
Remark. The norm ∥ x ∥ p , ∞ \|x\|_{p,\infty} ∥ x ∥ p , ∞ is the norm ∥ x ∥ ( p , ∞ ) \|x\|_{(p,\infty)} ∥ x ∥ ( p , ∞ ) of Bennett and Sharpley (1988, Chapter 4) on the weak-ℓ p \ell_p ℓ p sequence space, the Lorentz space ℓ p , ∞ \ell_{p,\infty} ℓ p , ∞ . It lies between the quasinorm sup i i 1 / p x ( i ) \sup_i i^{1/p}x_{(i)} sup i i 1/ p x ( i ) and p / ( p − 1 ) p/(p-1) p / ( p − 1 ) times that quasinorm.
The interpolation inequality
Proposition A.4. For p > 2 p>2 p > 2 , a vector x ≥ 0 x \ge0 x ≥ 0 with nonempty support U U U and ℓ : = ∣ U ∣ \ell:= |U| ℓ := ∣ U ∣ , and a nonnegative U × W U \times W U × W matrix B B B with column-sum bound B ∞ > 0 B_\infty>0 B ∞ > 0 (Definition 2.2), if γ > 0 \gamma>0 γ > 0 and a set Q ⊆ W Q \subseteq W Q ⊆ W of size m > 0 m>0 m > 0 satisfy
∑ u ∈ P i ( x ) ∑ w ∈ Q B u w ≤ γ i m ( 1 ≤ i ≤ ℓ ) , (11) \sum_{u \in P_i(x)} \sum_{w \in Q} B_{uw} \le\gamma\sqrt{im} \qquad(1 \le i \le\ell), \tag*{(11)} u ∈ P i ( x ) ∑ w ∈ Q ∑ B u w ≤ γ im ( 1 ≤ i ≤ ℓ ) , (11) then
∑ w ∈ Q ( x B ) ( w ) ≤ C p γ 2 / p B ∞ 1 − 2 / p ∥ x ∥ p , ∞ m 1 − 1 / p . (12) \sum_{w \in Q} (xB)(w) \le C_p\gamma^{2/p}B_\infty^{1-2/p}\|x\|_{p,\infty}m^{1-1/p}. \tag*{(12)} w ∈ Q ∑ ( x B ) ( w ) ≤ C p γ 2/ p B ∞ 1 − 2/ p ∥ x ∥ p , ∞ m 1 − 1/ p . (12)
Proof of Proposition A.4. We write U = { u 1 , … , u ℓ } U=\{u_1,\ldots,u_\ell\} U = { u 1 , … , u ℓ } in the order of Definition 2.1 and set c i : = ∑ w ∈ Q B u i , w c_i := \sum_{w \in Q} B_{u_i,w} c i := ∑ w ∈ Q B u i , w , so that ∑ w ∈ Q ( x B ) ( w ) = ∑ i = 1 ℓ x ( i ) c i \sum_{w \in Q}(xB)(w)=\sum_{i=1}^{\ell}x_{(i)}c_i ∑ w ∈ Q ( x B ) ( w ) = ∑ i = 1 ℓ x ( i ) c i . By (11) and the column-sum bound,
∑ j ≤ i c j ≤ g ( i ) ( 1 ≤ i ≤ ℓ ) , where g ( s ) : = min { γ m s , B ∞ m } ( s ≥ 0 ) . \sum_{j \le i} c_j \le g(i) \qquad(1 \le i \le\ell), \qquad\text{where } g(s):=\min\{\gamma\sqrt{ms},B_\infty m\}\qquad(s \ge0). j ≤ i ∑ c j ≤ g ( i ) ( 1 ≤ i ≤ ℓ ) , where g ( s ) := min { γ m s , B ∞ m } ( s ≥ 0 ) .
Then g ( 0 ) = 0 g(0)=0 g ( 0 ) = 0 , and the two terms defining g g g are equal at r : = B ∞ 2 m / γ 2 r := B_{\infty}^{2}m/\gamma^{2} r := B ∞ 2 m / γ 2 , so g ′ ( s ) = γ m / ( 2 s ) g'(s)=\gamma\sqrt{m}/(2\sqrt{s}) g ′ ( s ) = γ m / ( 2 s ) for 0 < s < r 0<s<r 0 < s < r and g ′ ( s ) = 0 g'(s)=0 g ′ ( s ) = 0 for s > r s>r s > r . By summation by parts, with x ( ℓ + 1 ) = 0 x(\ell+1)=0 x ( ℓ + 1 ) = 0 ,
∑ i = 1 ℓ x ( i ) c i = ∑ i = 1 ℓ ( x ( i ) − x ( i + 1 ) ) ∑ j ≤ i c j ≤ ∑ i = 1 ℓ ( x ( i ) − x ( i + 1 ) ) g ( i ) = ∑ i = 1 ℓ x ( i ) ( g ( i ) − g ( i − 1 ) ) . \sum_{i=1}^{\ell}x(i)c_i=\sum_{i=1}^{\ell}(x(i)-x(i+1))\sum_{j\leq i}c_j\leq\sum_{i=1}^{\ell}(x(i)-x(i+1))g(i)=\sum_{i=1}^{\ell}x(i)(g(i)-g(i-1)). i = 1 ∑ ℓ x ( i ) c i = i = 1 ∑ ℓ ( x ( i ) − x ( i + 1 )) j ≤ i ∑ c j ≤ i = 1 ∑ ℓ ( x ( i ) − x ( i + 1 )) g ( i ) = i = 1 ∑ ℓ x ( i ) ( g ( i ) − g ( i − 1 )) .
Since I x I_x I x is linear with slope x ( i ) x(i) x ( i ) on [ i − 1 , i ] [i-1,i] [ i − 1 , i ] and constant beyond ℓ \ell ℓ (Definition 2.1), we can write the last sum as an integral. Integrating by parts, with a zero boundary term at 0 because I x ( s ) = x ( 1 ) s I_x(s)=x(1)s I x ( s ) = x ( 1 ) s for 0 ≤ s ≤ 1 0\leq s\leq1 0 ≤ s ≤ 1 , we obtain
∑ w ∈ Q ( x B ) ( w ) ≤ ∫ 0 ∞ I x ′ ( s ) g ′ ( s ) d s = γ m 2 ∫ 0 r I x ′ ( s ) s d s = γ m 2 [ I x ( r ) r + 1 2 ∫ 0 r I x ( s ) s 3 / 2 d s ] . \sum_{w\in Q}(xB)(w)\leq\int_{0}^{\infty}I_x'(s)g'(s)\,\mathrm{d}s=\frac{\gamma\sqrt{m}}{2}\int_{0}^{r}\frac{I_x'(s)}{\sqrt{s}}\,\mathrm{d}s=\frac{\gamma\sqrt{m}}{2}\left[\frac{I_x(r)}{\sqrt{r}}+\frac{1}{2}\int_{0}^{r}\frac{I_x(s)}{s^{3/2}}\,\mathrm{d}s\right]. w ∈ Q ∑ ( x B ) ( w ) ≤ ∫ 0 ∞ I x ′ ( s ) g ′ ( s ) d s = 2 γ m ∫ 0 r s I x ′ ( s ) d s = 2 γ m [ r I x ( r ) + 2 1 ∫ 0 r s 3/2 I x ( s ) d s ] .
By Definition 2.1, I x ( s ) ≤ ∥ x ∥ p , ∞ s 1 − 1 / p I_x(s)\leq\lVert x\rVert_{p,\infty}s^{1-1/p} I x ( s ) ≤ ∥ x ∥ p , ∞ s 1 − 1/ p for every real s > 0 s>0 s > 0 . With τ : = 1 / 2 − 1 / p > 0 \tau:=1/2-1/p>0 τ := 1/2 − 1/ p > 0 , the bracketed expression is at most
∥ x ∥ p , ∞ ( r τ + 1 2 ∫ 0 r s τ − 1 d s ) = ∥ x ∥ p , ∞ r τ ( 1 + 1 2 τ ) = 2 C p ∥ x ∥ p , ∞ r τ . \lVert x\rVert_{p,\infty}\left(r^\tau+\frac{1}{2}\int_{0}^{r}s^{\tau-1}\,\mathrm{d}s\right)=\lVert x\rVert_{p,\infty}r^\tau\left(1+\frac{1}{2\tau}\right)=2C_p\lVert x\rVert_{p,\infty}r^\tau. ∥ x ∥ p , ∞ ( r τ + 2 1 ∫ 0 r s τ − 1 d s ) = ∥ x ∥ p , ∞ r τ ( 1 + 2 τ 1 ) = 2 C p ∥ x ∥ p , ∞ r τ .
Finally
γ m r τ = γ m ( B ∞ 2 m γ 2 ) 1 / 2 − 1 / p = γ 2 / p B ∞ 1 − 2 / p m 1 − 1 / p , \gamma\sqrt{m}r^\tau=\gamma\sqrt{m}\left(\frac{B_{\infty}^{2}m}{\gamma^{2}}\right)^{1/2-1/p}=\gamma^{2/p}B_{\infty}^{1-2/p}m^{1-1/p}, γ m r τ = γ m ( γ 2 B ∞ 2 m ) 1/2 − 1/ p = γ 2/ p B ∞ 1 − 2/ p m 1 − 1/ p ,
and (12) holds.
The restriction p > 2 p>2 p > 2 is needed only for τ > 0 \tau>0 τ > 0 , so that the integral of s τ − 1 s^{\tau-1} s τ − 1 converges at zero. For p = 2 p=2 p = 2 , the integrand is 1 / s 1/s 1/ s , whose integral over [ 1 , r ] [1,r] [ 1 , r ] is ln r \ln r ln r for r ≥ 1 r\geq1 r ≥ 1 , and we must bound the small prefixes separately, as in Appendix C.3.
The prefix-sum bound. The bound (2) in Section 2.1 is the case of Proposition A.4 in which B B B is the adjacency matrix A A A of a subgraph of G G G with column-sum bound B ∞ B_\infty B ∞ , x ≥ 0 x\geq0 x ≥ 0 is supported on L L L , y = x A y=xA y = x A , and Q = P m ( y ) Q=P_m(y) Q = P m ( y ) is a prefix of y y y . If d ( P i ( x ) , P m ( y ) ) ≤ σ d(P_i(x),P_m(y))\leq\sigma d ( P i ( x ) , P m ( y )) ≤ σ for every prefix P i ( x ) P_i(x) P i ( x ) , then
∑ u ∈ P i ( x ) ∑ w ∈ P m ( y ) A u w ≤ e ( P i ( x ) , P m ( y ) ) ≤ σ i m ( 1 ≤ i ≤ ℓ ) , \sum_{u\in P_i(x)}\sum_{w\in P_m(y)}A_{uw}\leq e(P_i(x),P_m(y))\leq\sigma\sqrt{im}\qquad(1\leq i\leq\ell), u ∈ P i ( x ) ∑ w ∈ P m ( y ) ∑ A u w ≤ e ( P i ( x ) , P m ( y )) ≤ σ im ( 1 ≤ i ≤ ℓ ) ,
which is (11) with γ = σ \gamma=\sigma γ = σ , and (12) is (2).
The one-step search bound
Lemma A.5 (Prefix sums after peeling). For p > 2 p>2 p > 2 , a , b , σ > 0 a,b,\sigma>0 a , b , σ > 0 , a vector x ≥ 0 x\geq0 x ≥ 0 with nonempty support U ⊆ L U\subseteq L U ⊆ L , the neighborhood graph H = ( U ∪ ˙ W , F ) H=(U\mathbin{\dot\cup}W,F) H = ( U ∪ ˙ W , F ) of U U U with W : = N G ( U ) W:=N_G(U) W := N G ( U ) , and a vector y y y returned by Peel ( H , x , a , b ) \operatorname{Peel}(H,x,a,b) Peel ( H , x , a , b ) , every nonempty Q ⊆ W Q\subseteq W Q ⊆ W with d ( P i ( x ) , Q ) ≤ σ d(P_i(x),Q)\leq\sigma d ( P i ( x ) , Q ) ≤ σ for all 1 ≤ i ≤ ∣ U ∣ 1\leq i\leq\lvert U\rvert 1 ≤ i ≤ ∣ U ∣ satisfies
∑ w ∈ Q y ( w ) ≤ ( 4 C p σ 2 b 2 ) 1 / p ∥ x ∥ p , ∞ ∣ Q ∣ 1 − 1 / p . \sum_{w\in Q}y(w)\leq\left(\frac{4C_p\sigma^2}{b^2}\right)^{1/p}\lVert x\rVert_{p,\infty}\lvert Q\rvert^{1-1/p}. w ∈ Q ∑ y ( w ) ≤ ( b 2 4 C p σ 2 ) 1/ p ∥ x ∥ p , ∞ ∣ Q ∣ 1 − 1/ p . The same bound holds for z : = prune ( δ , y ) z:=\operatorname{prune}(\delta,y) z := prune ( δ , y ) , for every δ > 0 \delta>0 δ > 0 . For U ⊆ R U\subseteq R U ⊆ R , the same holds with a a a and b b b exchanged, so that a 2 a^2 a 2 replaces b 2 b^2 b 2 in (13).
Proof of Lemma A.5. We write F ′ F' F ′ for the selected edges and B B B for the U × W U \times W U × W matrix with B u w : = 2 / b B_{uw} := 2/b B u w := 2/ b for u w ∈ F ′ uw \in F' u w ∈ F ′ and B u w : = 0 B_{uw} := 0 B u w := 0 otherwise, so that y = x B y = xB y = x B . Since Peel selects at most b / 2 b/2 b /2 edges incident to each w ∈ W w \in W w ∈ W ,
∑ u ∈ U B u w ≤ 1 ( w ∈ W ) . \sum_{u\in U} B_{uw} \le1 \qquad(w \in W). u ∈ U ∑ B u w ≤ 1 ( w ∈ W ) .
For every prefix P i ( x ) P_i(x) P i ( x ) ,
∑ u ∈ P i ( x ) ∑ w ∈ Q B u w ≤ 2 b e ( P i ( x ) , Q ) ≤ 2 σ b i ∣ Q ∣ . \sum_{u\in P_i(x)}\sum_{w\in Q} B_{uw} \le\frac{2}{b}e(P_i(x),Q) \le\frac{2\sigma}{b}\sqrt{i|Q|}. u ∈ P i ( x ) ∑ w ∈ Q ∑ B u w ≤ b 2 e ( P i ( x ) , Q ) ≤ b 2 σ i ∣ Q ∣ .
We apply Proposition A.4 with B ∞ = 1 B_\infty= 1 B ∞ = 1 and γ = 2 σ / b \gamma= 2\sigma/b γ = 2 σ / b to obtain (13). Since 0 ≤ z ≤ y 0 \le z \le y 0 ≤ z ≤ y , the same bound holds for z z z . \hfill □ \square □
With σ \sigma σ from (4) and Q = P m ( y ) Q = P_m(y) Q = P m ( y ) , (13) is (5).
Lemma A.6 (Scanning and returned sets). The following holds for one step of Search p \operatorname{Search}_p Search p with peeling parameters a , b > 0 a,b>0 a , b > 0 and density threshold σ > 0 \sigma>0 σ > 0 from a nonnegative vector x x x with nonempty support U ⊆ L U \subseteq L U ⊆ L , where W : = N G ( U ) W := N_G(U) W := N G ( U ) .
(a) If no star is returned, then the adjacency lists read in line 13 contain every edge of the neighborhood graph H H H of U U U (line 15), and deg ( u ) < σ 2 \deg(u) < \sigma^2 deg ( u ) < σ 2 for every u ∈ U u \in U u ∈ U .
(b) If Peel returns sets U ∗ ⊆ U U_* \subseteq U U ∗ ⊆ U and Y ⊆ W Y \subseteq W Y ⊆ W , both are nonempty and
∣ Y ∣ ≤ a ∣ U ∗ ∣ 2 b + 1 , d ( U ∗ , Y ) > a b / 8 . |Y| \le\frac{a|U_*|}{2b}+1,\qquad d(U_*,Y)>\sqrt{ab/8}. ∣ Y ∣ ≤ 2 b a ∣ U ∗ ∣ + 1 , d ( U ∗ , Y ) > ab /8 . For U ⊆ R U \subseteq R U ⊆ R , the same conclusions hold with a a a and b b b exchanged.
Proof of Lemma A.6. We prove each item below.
(a) If no star is returned, every adjacency list of a vertex in U U U is read to its end (line 14). Thus these lists contain every edge incident to U U U , and deg ( u ) ≤ ⌈ σ 2 ⌉ − 1 < σ 2 \deg(u) \le\lceil\sigma^2\rceil- 1 < \sigma^2 deg ( u ) ≤ ⌈ σ 2 ⌉ − 1 < σ 2 for every u ∈ U u \in U u ∈ U .
(b) Search p \operatorname{Search}_p Search p calls Peel only if no star is returned, so by (a), d H ( P , Q ) = d ( P , Q ) d_H(P,Q)=d(P,Q) d H ( P , Q ) = d ( P , Q ) for all P ⊆ U P \subseteq U P ⊆ U and Q ⊆ W Q \subseteq W Q ⊆ W . Both U ∗ U_* U ∗ and W ∗ W_* W ∗ are nonempty, since an isolated vertex would have been removed. Y Y Y is W ∗ W_* W ∗ or consists of ⌈ a ∣ U ∗ ∣ / ( 2 b ) ⌉ \lceil a|U_*|/(2b)\rceil ⌈ a ∣ U ∗ ∣/ ( 2 b )⌉ vertices of W ∗ W_* W ∗ (line 9), so Y Y Y is nonempty and
∣ Y ∣ ≤ ⌈ a ∣ U ∗ ∣ 2 b ⌉ ≤ a ∣ U ∗ ∣ 2 b + 1. |Y| \le\left\lceil\frac{a|U_*|}{2b}\right\rceil\le\frac{a|U_*|}{2b}+1. ∣ Y ∣ ≤ ⌈ 2 b a ∣ U ∗ ∣ ⌉ ≤ 2 b a ∣ U ∗ ∣ + 1.
If Y = W ∗ Y=W_* Y = W ∗ , then e H ( U ∗ , Y ) > ( a / 4 ) ∣ U ∗ ∣ e_H(U_*,Y)>(a/4)|U_*| e H ( U ∗ , Y ) > ( a /4 ) ∣ U ∗ ∣ and e H ( U ∗ , Y ) > ( b / 2 ) ∣ Y ∣ e_H(U_*,Y)>(b/2)|Y| e H ( U ∗ , Y ) > ( b /2 ) ∣ Y ∣ by the loop condition (line 2), so
d H ( U ∗ , Y ) 2 = e H ( U ∗ , Y ) ∣ U ∗ ∣ ⋅ e H ( U ∗ , Y ) ∣ Y ∣ > a 4 ⋅ b 2 = a b 8 . d_H(U_*,Y)^2
= \frac{e_H(U_*,Y)}{|U_*|}\cdot\frac{e_H(U_*,Y)}{|Y|}
> \frac{a}{4}\cdot\frac{b}{2}
= \frac{ab}{8}. d H ( U ∗ , Y ) 2 = ∣ U ∗ ∣ e H ( U ∗ , Y ) ⋅ ∣ Y ∣ e H ( U ∗ , Y ) > 4 a ⋅ 2 b = 8 ab .
If Y ≠ W ∗ Y \ne W_* Y = W ∗ , then ∣ Y ∣ = ⌈ a ∣ U ∗ ∣ / ( 2 b ) ⌉ |Y|=\lceil a|U_*|/(2b)\rceil ∣ Y ∣ = ⌈ a ∣ U ∗ ∣/ ( 2 b )⌉ , and every vertex of Y Y Y has more than b / 2 b/2 b /2 neighbors in U ∗ U_* U ∗ , so
d H ( U ∗ , Y ) > b 2 ∣ Y ∣ ∣ U ∗ ∣ ≥ b 2 a 2 b = a b / 8 . d_H(U_*,Y)>\frac{b}{2}\sqrt{\frac{|Y|}{|U_*|}}
\ge\frac{b}{2}\sqrt{\frac{a}{2b}}
=\sqrt{ab/8}. d H ( U ∗ , Y ) > 2 b ∣ U ∗ ∣ ∣ Y ∣ ≥ 2 b 2 b a = ab /8 .
\hfill □ \square □
Completing the analysis of the local algorithm
We complete the proof of Theorem 1.2 and prove Corollary B.4.
Search invariants and termination
Lemma B.1. For p > 2 p > 2 p > 2 , k ≥ 1 k \ge1 k ≥ 1 , a , b ∈ [ 1 , k ] a,b \in[1,k] a , b ∈ [ 1 , k ] and a vertex v ∈ L v \in L v ∈ L of positive degree, Search p ( G , v , k , a , b ) \operatorname{Search}_{p}(G,v,k,a,b) Search p ( G , v , k , a , b ) with the parameters in (4) satisfies the following.
(a) Every vector x t x_t x t satisfies ∥ x t ∥ p , ∞ ≤ K t 1 / p \|x_t\|_{p,\infty} \le K_t^{1/p} ∥ x t ∥ p , ∞ ≤ K t 1/ p .
(b) Every positive coordinate of x t x_t x t is at least δ \delta δ , and ∣ supp ( x t ) ∣ ≤ K t / δ p ≤ ( 4 k ) p ( 3 / 4 ) t |\operatorname{supp}(x_t)| \le K_t/\delta^p \le(4k)^p(3/4)^t ∣ supp ( x t ) ∣ ≤ K t / δ p ≤ ( 4 k ) p ( 3/4 ) t .
(c) The search terminates and never returns ⊥ \perp ⊥ from the sweep.
(d) In each step, the search reads at most ⌈ σ 2 ⌉ ≤ a b \lceil\sigma^2\rceil\le ab ⌈ σ 2 ⌉ ≤ ab entries of each adjacency list. Whenever the search returns sets X , Y X,Y X , Y , they satisfy d ( X , Y ) ≥ σ d(X,Y) \ge\sigma d ( X , Y ) ≥ σ and ∣ X ∣ , ∣ Y ∣ ≤ ( 4 k ) p |X|,|Y| \le(4k)^p ∣ X ∣ , ∣ Y ∣ ≤ ( 4 k ) p .
For v ∈ R v \in R v ∈ R , the same holds for the search with L L L and R R R exchanged.
Proof of Lemma B.1. We prove each item below.
(a) ∥ x 0 ∥ p , ∞ = 1 = K 0 1 / p \|x_0\|_{p,\infty} = 1 = K_0^{1/p} ∥ x 0 ∥ p , ∞ = 1 = K 0 1/ p , and every later x t x_t x t satisfies the weak-norm test ∥ x t ∥ p , ∞ ≤ K t 1 / p \|x_t\|_{p,\infty} \le K_t^{1/p} ∥ x t ∥ p , ∞ ≤ K t 1/ p (line 20).
(b) Positive coordinates are at least δ \delta δ at t = 0 t = 0 t = 0 , since x 0 = 1 v x_0 = \mathbf{1}_v x 0 = 1 v and δ = max { 1 , a / b } / ( 4 k ) ≤ 1 / 4 \delta= \max\{1,a/b\}/(4k) \le1/4 δ = max { 1 , a / b } / ( 4 k ) ≤ 1/4 , and at later steps by pruning (Lemma A.3 (c)). By (a) and Lemma A.3 (b), ∣ supp ( x t ) ∣ ≤ ∥ x t ∥ p , ∞ / δ p ≤ K t / δ p |\operatorname{supp}(x_t)| \le\|x_t\|_{p,\infty}/\delta^p \le K_t/\delta^p ∣ supp ( x t ) ∣ ≤ ∥ x t ∥ p , ∞ / δ p ≤ K t / δ p . Since δ ≥ 1 / ( 4 k ) \delta\ge1/(4k) δ ≥ 1/ ( 4 k ) and K t ≤ 4 k δ ( 3 / 4 ) t K_t \le4k\delta(3/4)^t K t ≤ 4 k δ ( 3/4 ) t by (4) ,
K t δ p ≤ 4 k δ 1 − p ( 3 4 ) t ≤ ( 4 k ) p ( 3 4 ) t . (13) \frac{K_t}{\delta^p} \le4k\delta^{1-p}\left(\frac{3}{4}\right)^t \le(4k)^p\left(\frac{3}{4}\right)^t . \tag*{(13)} δ p K t ≤ 4 k δ 1 − p ( 4 3 ) t ≤ ( 4 k ) p ( 4 3 ) t . (13)
(c) Every vector x t x_t x t is nonzero (line 19), so, by (b), 1 ≤ ∣ supp ( x t ) ∣ ≤ ( 4 k ) p ( 3 / 4 ) t 1 \le|\operatorname{supp}(x_t)| \le(4k)^p(3/4)^t 1 ≤ ∣ supp ( x t ) ∣ ≤ ( 4 k ) p ( 3/4 ) t . The upper bound tends to zero, so the search computes only finitely many vectors x t x_t x t and terminates.
For the second claim of (c), we show that in the sweep at step t t t we find i i i with d ( P i ( x t ) , P m ( z ) ) > σ d(P_i(x_t),P_m(z)) > \sigma d ( P i ( x t ) , P m ( z )) > σ , where z = prune ( δ , y t + 1 ) z = \operatorname{prune}(\delta,y_{t+1}) z = prune ( δ , y t + 1 ) and P m ( z ) P_m(z) P m ( z ) is the prefix of line 23. Otherwise, for even t t t , by Lemma A.5 with Q = P m ( z ) Q = P_m(z) Q = P m ( z ) and by (a),
I z ( m ) ≤ ( 4 C p σ 2 b 2 ) 1 / p K t 1 / p m 1 − 1 / p . I_z(m) \le\left(\frac{4C_p\sigma^2}{b^2}\right)^{1/p} K_t^{1/p}m^{1-1/p}. I z ( m ) ≤ ( b 2 4 C p σ 2 ) 1/ p K t 1/ p m 1 − 1/ p .
By (4) , 4 C p σ 2 = 3 a b / 4 4C_p\sigma^2 = 3ab/4 4 C p σ 2 = 3 ab /4 , so the factor is ( 3 a / ( 4 b ) ) 1 / p = ( K t + 1 / K t ) 1 / p (3a/(4b))^{1/p} = (K_{t+1}/K_t)^{1/p} ( 3 a / ( 4 b ) ) 1/ p = ( K t + 1 / K t ) 1/ p . For odd t t t , (13) holds with a 2 a^2 a 2 in place of b 2 b^2 b 2 , and the factor is ( 3 b / ( 4 a ) ) 1 / p = ( K t + 1 / K t ) 1 / p (3b/(4a))^{1/p} = (K_{t+1}/K_t)^{1/p} ( 3 b / ( 4 a ) ) 1/ p = ( K t + 1 / K t ) 1/ p . In both cases, I z ( m ) ≤ K t + 1 1 / p m 1 − 1 / p I_z(m) \le K_{t+1}^{1/p}m^{1-1/p} I z ( m ) ≤ K t + 1 1/ p m 1 − 1/ p , contradicting the choice of m m m . The graph H H H is the neighborhood graph of supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) (line 15), so d H ( P i ( x t ) , P m ( z ) ) = d ( P i ( x t ) , P m ( z ) ) > σ d_H(P_i(x_t),P_m(z)) = d(P_i(x_t),P_m(z)) > \sigma d H ( P i ( x t ) , P m ( z )) = d ( P i ( x t ) , P m ( z )) > σ , and the sets P i ( x t ) , P m ( z ) P_i(x_t),P_m(z) P i ( x t ) , P m ( z ) are returned by the sweep.
(d) In each step, the search reads at most ⌈ σ 2 ⌉ \lceil\sigma^2\rceil ⌈ σ 2 ⌉ entries of each adjacency list (line 13). By Bernoulli’s inequality, C p p = ( 1 + 1 p − 2 ) p ≥ 1 + p p − 2 > 2 C_p^p = (1 + \frac{1}{p-2})^p \ge1 + \frac{p}{p-2} > 2 C p p = ( 1 + p − 2 1 ) p ≥ 1 + p − 2 p > 2 , so σ 2 = 3 a b / ( 16 C p p ) < a b / 8 \sigma^2 = 3ab/(16C_p^p) < ab/8 σ 2 = 3 ab / ( 16 C p p ) < ab /8 , and since a b ≥ 1 ab \ge1 ab ≥ 1 , it follows that ⌈ σ 2 ⌉ ≤ ⌈ a b / 8 ⌉ ≤ a b ≤ k 2 ≤ ( 4 k ) p \lceil\sigma^2\rceil\le\lceil ab/8\rceil\le ab \le k^2 \le(4k)^p ⌈ σ 2 ⌉ ≤ ⌈ ab /8 ⌉ ≤ ab ≤ k 2 ≤ ( 4 k ) p . A returned star therefore has at most ( 4 k ) p (4k)^p ( 4 k ) p leaves, and its density is ⌈ σ 2 ⌉ ≥ σ \sqrt{\lceil\sigma^2\rceil} \ge\sigma ⌈ σ 2 ⌉ ≥ σ . The sets returned by the sweep have density above σ \sigma σ (line 24), and the sets returned by peeling have density above a b / 8 > σ \sqrt{ab/8} > \sigma ab /8 > σ (Lemma A.6(b)).
For sets P i ( x t ) , P m ( z ) P_i(x_t),P_m(z) P i ( x t ) , P m ( z ) returned by the sweep at step t t t , the prefix P i ( x t ) P_i(x_t) P i ( x t ) lies in supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) , so i ≤ ( 4 k ) p i \le(4k)^p i ≤ ( 4 k ) p by (b). By Lemma A.3 (a), m ≤ ∣ supp ( z ) ∣ m \le|\operatorname{supp}(z)| m ≤ ∣ supp ( z ) ∣ , so z ( m ) ≥ δ z(m) \ge\delta z ( m ) ≥ δ by pruning, and since m m m is the smallest index with I z ( m ) > K t + 1 1 / p m 1 − 1 / p I_z(m) > K_{t+1}^{1/p}m^{1-1/p} I z ( m ) > K t + 1 1/ p m 1 − 1/ p ,
( m − 1 ) δ ≤ I z ( m − 1 ) ≤ K t + 1 1 / p ( m − 1 ) 1 − 1 / p , (m-1)\delta\le I_z(m-1) \le K_{t+1}^{1/p}(m-1)^{1-1/p}, ( m − 1 ) δ ≤ I z ( m − 1 ) ≤ K t + 1 1/ p ( m − 1 ) 1 − 1/ p ,
so, by (14) and ( 4 k ) p ≥ 16 (4k)^p \ge16 ( 4 k ) p ≥ 16 ,
m ≤ K t + 1 δ p + 1 ≤ 3 4 ( 4 k ) p + 1 ≤ ( 4 k ) p . m \le\frac{K_{t+1}}{\delta^p}+1 \le\frac{3}{4}(4k)^p+1 \le(4k)^p. m ≤ δ p K t + 1 + 1 ≤ 4 3 ( 4 k ) p + 1 ≤ ( 4 k ) p .
For sets U ∗ , Y U_*,Y U ∗ , Y returned by peeling at step t t t , the set U ∗ U_* U ∗ lies in supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) , so ∣ U ∗ ∣ ≤ K t / δ p |U_*| \le K_t/\delta^p ∣ U ∗ ∣ ≤ K t / δ p by (b). By Lemma A.6(b), ∣ Y ∣ ≤ a ∣ U ∗ ∣ / ( 2 b ) + 1 |Y| \le a|U_*|/(2b)+1 ∣ Y ∣ ≤ a ∣ U ∗ ∣/ ( 2 b ) + 1 for even t t t , and ∣ Y ∣ ≤ b ∣ U ∗ ∣ / ( 2 a ) + 1 |Y| \le b|U_*|/(2a)+1 ∣ Y ∣ ≤ b ∣ U ∗ ∣/ ( 2 a ) + 1 for odd t t t . In both cases, the coefficient of ∣ U ∗ ∣ |U_*| ∣ U ∗ ∣ is 2 K t + 1 / ( 3 K t ) 2K_{t+1}/(3K_t) 2 K t + 1 / ( 3 K t ) by (4). Hence, by (14),
∣ Y ∣ ≤ 2 K t + 1 3 K t ∣ U ∗ ∣ + 1 ≤ 2 K t + 1 3 δ p + 1 ≤ ( 4 k ) p 2 + 1 ≤ ( 4 k ) p . |Y| \le\frac{2K_{t+1}}{3K_t}|U_*|+1 \le\frac{2K_{t+1}}{3\delta^p}+1 \le\frac{(4k)^p}{2}+1 \le(4k)^p. ∣ Y ∣ ≤ 3 K t 2 K t + 1 ∣ U ∗ ∣ + 1 ≤ 3 δ p 2 K t + 1 + 1 ≤ 2 ( 4 k ) p + 1 ≤ ( 4 k ) p .
Query complexity, running time, and locality
Graph access. The algorithm accesses G G G through neighbor queries. Each adjacency list has a fixed order. When the algorithm makes a query ( u , i ) (u,i) ( u , i ) for an integer i ≥ 1 i \ge1 i ≥ 1 , it receives the i i i th neighbor of u u u , or ⊥ \perp ⊥ if i > deg ( u ) i > \deg(u) i > deg ( u ) , where deg ( u ) \deg(u) deg ( u ) is the degree of u u u . To read the list to its end, the algorithm makes deg ( u ) + 1 \deg(u)+1 deg ( u ) + 1 queries. We assume that the side of a vertex can be read from its identifier. We count neighbor queries and elementary operations at unit cost, including reads, copies, and comparisons of vertex identifiers. For Θ ( log ∣ V ∣ ) \Theta(\log|V|) Θ ( log ∣ V ∣ ) -bit identifiers, reading an identifier takes Θ ( log ∣ V ∣ ) \Theta(\log|V|) Θ ( log ∣ V ∣ ) bit operations.
Theorem B.2 (Local computation). For p > 2 p > 2 p > 2 , k ≥ 1 k \ge1 k ≥ 1 and every starting vertex v v v , the algorithm LocalDensep ( G , v , k ) _p(G,v,k) p ( G , v , k ) terminates. If v v v is isolated, it returns ⊥ \perp ⊥ after one query. Otherwise, the output has at most 2 ( 4 k ) p 2(4k)^p 2 ( 4 k ) p vertices and density at least one, the number of neighbor queries is at most
1 + 4 ( 4 k ) p min { ( Δ + 1 ) ( 1 + ⌊ log 2 k ⌋ ) 2 , 4 k 2 } , (14) 1+4(4k)^p\min\left\{(\Delta+1)(1+\lfloor\log_2 k\rfloor)^2,4k^2\right\}, \tag*{(14)} 1 + 4 ( 4 k ) p min { ( Δ + 1 ) ( 1 + ⌊ log 2 k ⌋ ) 2 , 4 k 2 } , (14) and the running time is
O p ( min { Δ k p log 2 3 ( 2 k ) , k p + 2 log 2 ( 2 k ) } ) . (15) O_p\left(\min\left\{\Delta k^p\log_2^3(2k),k^{p+2}\log_2(2k)\right\}\right). \tag*{(15)} O p ( min { Δ k p log 2 3 ( 2 k ) , k p + 2 log 2 ( 2 k ) } ) . (15)
Proof of Theorem B.2. If v v v is isolated, the first query is answered with ⊥ \perp ⊥ , and LocalDensep _p p returns ⊥ \perp ⊥ as well (line 2). Otherwise, every search terminates by Lemma B.1(c). By Lemma B.1(d), the sets returned by the searches have at most ( 4 k ) p (4k)^p ( 4 k ) p vertices per side, so the output has at most 2 ( 4 k ) p 2(4k)^p 2 ( 4 k ) p vertices. Its density is at least one because the initial edge is a candidate.
By Lemma B.1(b), for each guess ( a , b ) (a,b) ( a , b ) , the algorithm scans at most ∑ t ∣ supp ( x t ) ∣ ≤ 4 ( 4 k ) p \sum_t|\operatorname{supp}(x_t)| \le4(4k)^p ∑ t ∣ supp ( x t ) ∣ ≤ 4 ( 4 k ) p adjacency lists in total, with at most min { Δ + 1 , ⌈ σ 2 ⌉ } ≤ min { Δ + 1 , a b } \min\{\Delta+1,\lceil\sigma^2\rceil\} \le\min\{\Delta+1,ab\} min { Δ + 1 , ⌈ σ 2 ⌉} ≤ min { Δ + 1 , ab } queries per list by Lemma B.1(d). Including the initial query, the total is at most
1 + 4 ( 4 k ) p ∑ a , b min { Δ + 1 , a b } , 1+4(4k)^p\sum_{a,b}\min\{\Delta+1,ab\}, 1 + 4 ( 4 k ) p a , b ∑ min { Δ + 1 , ab } ,
where there are ( 1 + ⌊ log 2 k ⌋ ) 2 (1+\lfloor\log_2 k\rfloor)^2 ( 1 + ⌊ log 2 k ⌋ ) 2 guesses and
∑ a , b a b = ( ∑ j = 0 ⌊ log 2 k ⌋ 2 j ) 2 < 4 k 2 . \sum_{a,b}ab=\left(\sum_{j=0}^{\lfloor\log_2 k\rfloor}2^j\right)^2<4k^2. a , b ∑ ab = j = 0 ∑ ⌊ l o g 2 k ⌋ 2 j 2 < 4 k 2 .
Thus the number of queries is at most (15).
For the running time, we consider a step in which no star is returned, with the neighborhood graph H = ( U ∪ ˙ W , F ) H=(U\mathbin{\dot\cup}W,F) H = ( U ∪ ˙ W , F ) of U : = supp ( x t ) U:=\operatorname{supp}(x_t) U := supp ( x t ) . Every vertex of U U U has a neighbor, since v v v has positive degree and every vertex of supp ( x t + 1 ) \operatorname{supp}(x_{t+1}) supp ( x t + 1 ) is joined to supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) by a selected edge (line 8), so $|U|+|W| \le 2 ∣ F ∣ 2|F| 2∣ F ∣ . By Lemma B.1(b), ∣ U ∣ ≤ ( 4 k ) p |U| \le(4k)^p ∣ U ∣ ≤ ( 4 k ) p , and by Lemma A.6(a) and (4), deg ( u ) < σ 2 < a b ≤ k 2 \deg(u) < \sigma^2 < ab \le k^2 deg ( u ) < σ 2 < ab ≤ k 2 for every u ∈ U u \in U u ∈ U , so
∣ F ∣ = ∑ u ∈ U deg ( u ) < k 2 ( 4 k ) p . |F| = \sum_{u\in U} \deg(u) < k^2(4k)^p. ∣ F ∣ = u ∈ U ∑ deg ( u ) < k 2 ( 4 k ) p .
The time spent in this step sorting the vectors, running Peel and performing any sweep is O ( ∣ F ∣ log 2 ∣ F ∣ ) = O p ( ∣ F ∣ log 2 ( 2 k ) ) O(|F|\log_2 |F|)=O_p(|F|\log_2(2k)) O ( ∣ F ∣ log 2 ∣ F ∣ ) = O p ( ∣ F ∣ log 2 ( 2 k )) , and the algorithm makes at least ∣ F ∣ |F| ∣ F ∣ queries to build H H H . When a star is returned, the work in that step is linear in the number of queries. Summing over all steps and guesses, we obtain a time bound of O p ( log 2 ( 2 k ) ) O_p(\log_2(2k)) O p ( log 2 ( 2 k )) per query and hence (16).
Lemma B.3 (Distance from the starting vertex). For sets X ⊆ L X \subseteq L X ⊆ L and Y ⊆ R Y \subseteq R Y ⊆ R returned by LocalDense p ( G , v , k ) \operatorname{LocalDense}_p(G,v,k) LocalDense p ( G , v , k ) , every vertex of X ∪ ˙ Y X \mathbin{\dot\cup} Y X ∪ ˙ Y lies within distance 1 + p log 2 ( 4 k ) / log 2 ( 4 / 3 ) 1+p\log_2(4k)/\log_2(4/3) 1 + p log 2 ( 4 k ) / log 2 ( 4/3 ) of v v v in G G G . If v ∈ L v\in L v ∈ L then d ( X ∪ { v } , Y ) ≥ d ( X , Y ) / 2 d(X\cup\{v\},Y)\ge d(X,Y)/\sqrt{2} d ( X ∪ { v } , Y ) ≥ d ( X , Y ) / 2 , and if v ∈ R v\in R v ∈ R then d ( X , Y ∪ { v } ) ≥ d ( X , Y ) / 2 d(X,Y\cup\{v\})\ge d(X,Y)/\sqrt{2} d ( X , Y ∪ { v }) ≥ d ( X , Y ) / 2 .
Proof of Lemma B.3. In every search, supp ( x 0 ) = { v } \operatorname{supp}(x_0)=\{v\} supp ( x 0 ) = { v } , and every vertex of supp ( x t + 1 ) \operatorname{supp}(x_{t+1}) supp ( x t + 1 ) has a neighbor in supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) , since y t + 1 y_{t+1} y t + 1 is indexed by N G ( supp ( x t ) ) N_G(\operatorname{supp}(x_t)) N G ( supp ( x t )) and x t + 1 ≤ y t + 1 x_{t+1}\le y_{t+1} x t + 1 ≤ y t + 1 . By induction, supp ( x t ) \operatorname{supp}(x_t) supp ( x t ) lies within distance t t t of v v v . At step t t t , the vertices of a returned star, of the sets returned by peeling and of the prefixes returned by the sweep lie in supp ( x t ) ∪ N G ( supp ( x t ) ) \operatorname{supp}(x_t)\cup N_G(\operatorname{supp}(x_t)) supp ( x t ) ∪ N G ( supp ( x t )) and hence within distance t + 1 t+1 t + 1 of v v v . The initial edge is within distance one of v v v . Every vector x t x_t x t is nonzero, so 1 ≤ ∣ supp ( x t ) ∣ ≤ ( 4 k ) p ( 3 / 4 ) t 1\le|\operatorname{supp}(x_t)|\le(4k)^p(3/4)^t 1 ≤ ∣ supp ( x t ) ∣ ≤ ( 4 k ) p ( 3/4 ) t by Lemma B.1(b), and thus t ≤ p log 2 ( 4 k ) / log 2 ( 4 / 3 ) t\le p\log_2(4k)/\log_2(4/3) t ≤ p log 2 ( 4 k ) / log 2 ( 4/3 ) .
For the last claim, if v ∈ L v\in L v ∈ L , then e ( X ∪ { v } , Y ) ≥ e ( X , Y ) e(X\cup\{v\},Y)\ge e(X,Y) e ( X ∪ { v } , Y ) ≥ e ( X , Y ) and ∣ X ∪ { v } ∣ ≤ 2 ∣ X ∣ |X\cup\{v\}|\le2|X| ∣ X ∪ { v } ∣ ≤ 2∣ X ∣ , so d ( X ∪ { v } , Y ) ≥ d ( X , Y ) / 2 d(X\cup\{v\},Y)\ge d(X,Y)/\sqrt{2} d ( X ∪ { v } , Y ) ≥ d ( X , Y ) / 2 . The case v ∈ R v\in R v ∈ R is symmetric.
Choosing the exponent
Proof of Theorem 1.2. For every p > 2 p>2 p > 2 , LocalDense p ( G , v , k ) \operatorname{LocalDense}_p(G,v,k) LocalDense p ( G , v , k ) returns nonempty sets X ⊆ L X\subseteq L X ⊆ L and Y ⊆ R Y\subseteq R Y ⊆ R with
d ( X , Y ) > 3 16 C p − p / 2 d ( S , T ) , C p = 1 + 1 p − 2 . d(X,Y)>\frac{\sqrt{3}}{16}C_p^{-p/2}d(S,T),\qquad C_p=1+\frac{1}{p-2}. d ( X , Y ) > 16 3 C p − p /2 d ( S , T ) , C p = 1 + p − 2 1 .
as proved in Section 2.3. For ϵ > 0 \epsilon>0 ϵ > 0 and p : = 2 + ϵ p:=2+\epsilon p := 2 + ϵ , the constant C p C_p C p equals 1 + 1 / ϵ 1+1/\epsilon 1 + 1/ ϵ . By ln ( 1 + 1 / ϵ ) ≤ 1 / ϵ \ln(1+1/\epsilon)\le1/\epsilon ln ( 1 + 1/ ϵ ) ≤ 1/ ϵ ,
C p − p / 2 = ( ϵ 1 + ϵ ) 1 + ϵ / 2 = ϵ 1 + ϵ ( 1 + 1 ϵ ) − ϵ / 2 ≥ ϵ e ( 1 + ϵ ) . (16) C_p^{-p/2}=\left(\frac{\epsilon}{1+\epsilon}\right)^{1+\epsilon/2}
=\frac{\epsilon}{1+\epsilon}\left(1+\frac{1}{\epsilon}\right)^{-\epsilon/2}
\ge\frac{\epsilon}{\sqrt{e}(1+\epsilon)}. \tag*{(16)} C p − p /2 = ( 1 + ϵ ϵ ) 1 + ϵ /2 = 1 + ϵ ϵ ( 1 + ϵ 1 ) − ϵ /2 ≥ e ( 1 + ϵ ) ϵ . (16)
Hence d ( X , Y ) > 3 16 e ϵ 1 + ϵ d ( S , T ) d(X,Y)>\frac{\sqrt{3}}{16\sqrt{e}}\frac{\epsilon}{1+\epsilon}d(S,T) d ( X , Y ) > 16 e 3 1 + ϵ ϵ d ( S , T ) , which is (ii) of Theorem 1.2. By Theorem B.2, the output has O ϵ ( k 2 + ϵ ) O_\epsilon(k^{2+\epsilon}) O ϵ ( k 2 + ϵ ) vertices, and the algorithm makes O ϵ ( k 2 + ϵ min { Δ log 2 2 ( 2 k ) , k 2 } ) O_\epsilon(k^{2+\epsilon}\min\{\Delta\log_2^2(2k),k^2\}) O ϵ ( k 2 + ϵ min { Δ log 2 2 ( 2 k ) , k 2 }) neighbor queries and runs in time O ~ ϵ ( k 2 + ϵ min { Δ , k 2 } ) \widetilde{O}_\epsilon(k^{2+\epsilon}\min\{\Delta,k^2\}) O ϵ ( k 2 + ϵ min { Δ , k 2 }) , as claimed in Theorem 1.2.
Corollary B.4 (Quadratic output size). For cohesive sets S ⊆ L S\subseteq L S ⊆ L and T ⊆ R T\subseteq R T ⊆ R , k ≥ 1 k\ge1 k ≥ 1 with ∣ S ∣ , ∣ T ∣ ≤ k |S|,|T|\le k ∣ S ∣ , ∣ T ∣ ≤ k , a vertex v ∈ S ∪ ˙ T v\in S\mathbin{\dot\cup}T v ∈ S ∪ ˙ T , ϵ : = 1 / ⌈ log 2 ( 2 k ) ⌉ \epsilon:=1/\lceil\log_2(2k)\rceil ϵ := 1/ ⌈ log 2 ( 2 k )⌉ and p : = 2 + ϵ p:=2+\epsilon p := 2 + ϵ , the algorithm LocalDense p ( G , v , k ) \operatorname{LocalDense}_p(G,v,k) LocalDense p ( G , v , k ) returns nonempty sets X ⊆ L X\subseteq L X ⊆ L and Y ⊆ R Y\subseteq R Y ⊆ R with ∣ X ∣ + ∣ Y ∣ ≤ 128 k 2 |X|+|Y|\le128k^2 ∣ X ∣ + ∣ Y ∣ ≤ 128 k 2 and
d ( X , Y ) > 6 128 d ( S , T ) log 2 ( 2 k ) . d(X,Y)>\frac{\sqrt{6}}{128}\frac{d(S,T)}{\log_2(2k)}. d ( X , Y ) > 128 6 log 2 ( 2 k ) d ( S , T ) .
For every starting vertex, the number of neighbor queries is at most
1 + 256 k 2 min { ( Δ + 1 ) ( 1 + ⌊ log 2 k ⌋ ) 2 , 4 k 2 } . 1+256k^2\min\left\{(\Delta+1)(1+\lfloor\log_2 k\rfloor)^2,4k^2\right\}. 1 + 256 k 2 min { ( Δ + 1 ) ( 1 + ⌊ log 2 k ⌋ ) 2 , 4 k 2 } .
Proof of Corollary B.4. The choice ϵ = 1 / ⌈ log 2 ( 2 k ) ⌉ \epsilon= 1/\lceil\log_{2}(2k) \rceil ϵ = 1/ ⌈ log 2 ( 2 k )⌉ satisfies 1 / ( 2 log 2 ( 2 k ) ) ≤ ϵ ≤ 1 1/(2\log_{2}(2k)) \le\epsilon\le1 1/ ( 2 log 2 ( 2 k )) ≤ ϵ ≤ 1 and 2 1 / ϵ ≥ 1 + 1 / ϵ 2^{1/\epsilon} \ge1 + 1/\epsilon 2 1/ ϵ ≥ 1 + 1/ ϵ . By the identity in (17),
C p − p / 2 ≥ ϵ 2 2 ≥ 1 4 2 log 2 ( 2 k ) . C_{p}^{-p/2} \ge\frac{\epsilon}{2\sqrt{2}} \ge\frac{1}{4\sqrt{2}\log_{2}(2k)}. C p − p /2 ≥ 2 2 ϵ ≥ 4 2 log 2 ( 2 k ) 1 .
By this inequality and (7), d ( X , Y ) > 6 128 d ( S , T ) / log 2 ( 2 k ) d(X,Y) > \frac{\sqrt{6}}{128}d(S,T)/\log_{2}(2k) d ( X , Y ) > 128 6 d ( S , T ) / log 2 ( 2 k ) . Since log 2 ( 2 k ) ≥ 1 \log_{2}(2k) \ge1 log 2 ( 2 k ) ≥ 1 , log 2 ( 4 k ) = log 2 ( 2 k ) + 1 ≤ 2 ⌈ log 2 ( 2 k ) ⌉ \log_{2}(4k) = \log_{2}(2k) + 1 \le2\lceil\log_{2}(2k)\rceil log 2 ( 4 k ) = log 2 ( 2 k ) + 1 ≤ 2 ⌈ log 2 ( 2 k )⌉ , and hence
( 4 k ) ϵ = 2 log 2 ( 4 k ) / ⌈ log 2 ( 2 k ) ⌉ ≤ 2 2 = 4. (4k)^{\epsilon} = 2^{\log_{2}(4k)/\lceil\log_{2}(2k)\rceil} \le2^{2} = 4. ( 4 k ) ϵ = 2 l o g 2 ( 4 k ) / ⌈ l o g 2 ( 2 k )⌉ ≤ 2 2 = 4.
Thus ( 4 k ) p ≤ 64 k 2 (4k)^{p} \le64k^{2} ( 4 k ) p ≤ 64 k 2 , and by Theorem B.2 there are at most 2 ( 4 k ) p ≤ 128 k 2 2(4k)^{p} \le128k^{2} 2 ( 4 k ) p ≤ 128 k 2 output vertices. Substituting ( 4 k ) p ≤ 64 k 2 (4k)^{p} \le64k^{2} ( 4 k ) p ≤ 64 k 2 into (15), we get the query bound in Corollary B.4.
The logarithmic factor at p = 2 p = 2 p = 2 and comparison with Andersen
Andersen’s guarantee has two parts: growth of the Euclidean norm inside a dense bipartite subgraph, and extraction of a dense bipartite subgraph from that growth (Appendix C.1). After recalling his iteration and the two lemmas, we describe the neighbor-query implementation of his algorithm in Appendix C.2. With the weak-ℓ 2 \ell_{2} ℓ 2 bound ∣ x ( i ) ∣ ≤ i |x(i)| \le\sqrt{i} ∣ x ( i ) ∣ ≤ i in place of the bound on ∥ x ∥ p , ∞ \lVert x\rVert_{p,\infty} ∥ x ∥ p , ∞ , we incur a logarithmic factor in the prefix-sum argument of Section 2.1 (Appendix C.3), and there is a weighted matrix for which the logarithmic factor in the extraction is necessary (Appendix C.4).
Andersen’s growth and extraction lemmas
Andersen’s iteration. Andersen’s algorithm runs the pruned growth process ([2 Definition 5] ) for t 0 : = ⌈ log 2 ( 2 k ) ⌉ t_{0} := \lceil\log_{2}(2\sqrt{k})\rceil t 0 := ⌈ log 2 ( 2 k )⌉ steps. Starting from x 0 : = 1 v x_{0} := \mathbf{1}_{v} x 0 := 1 v , with the pruning thresholds δ t + 1 > 0 \delta_{t+1} > 0 δ t + 1 > 0 of that definition and the adjacency matrix A A A of G G G , it computes
y t + 1 : = x t A ∥ x t A ∥ 2 , x t + 1 : = prune ( δ t + 1 , y t + 1 ) . y_{t+1} := \frac{x_{t}A}{\lVert x_{t}A\rVert_{2}}, \qquad x_{t+1} := \operatorname{prune}(\delta_{t+1},y_{t+1}). y t + 1 := ∥ x t A ∥ 2 x t A , x t + 1 := prune ( δ t + 1 , y t + 1 ) .
Each y t + 1 y_{t+1} y t + 1 is a unit vector, so ∥ x t ∥ 2 ≤ 1 \lVert x_{t}\rVert_{2} \le1 ∥ x t ∥ 2 ≤ 1 .
Definition C.1 (Dyadic level sets [2 Definition 6] ). For a nonnegative vector x x x , its dyadic level sets are D j ( x ) : = { u : 2 − j − 1 < x ( u ) ≤ 2 − j } D_{j}(x) := \{u : 2^{-j-1} < x(u) \le2^{-j}\} D j ( x ) := { u : 2 − j − 1 < x ( u ) ≤ 2 − j } for j ∈ Z j \in\mathbb{Z} j ∈ Z .
At each step 0 ≤ t < t 0 0 \le t < t_{0} 0 ≤ t < t 0 , Andersen’s algorithm tests the nonempty sets
X : = D i ( x t ∥ x t ∥ 2 ) , Y : = D j ( x t A ∥ x t A ∥ 2 ) with ∣ i − j ∣ ≤ 4 + log 2 Δ . X := D_{i}\left(\frac{x_{t}}{\lVert x_{t}\rVert_{2}}\right), \qquad Y := D_{j}\left(\frac{x_{t}A}{\lVert x_{t}A\rVert_{2}}\right) \quad\text{with } |i-j| \le4 + \log_{2}\Delta. X := D i ( ∥ x t ∥ 2 x t ) , Y := D j ( ∥ x t A ∥ 2 x t A ) with ∣ i − j ∣ ≤ 4 + log 2 Δ. It returns the tested sets X , Y X,Y X , Y of maximum density.
Lemma C.2 (Growth inside a dense bipartite subgraph [2 Lemma 2 and proof of Theorem 1] ). For S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R with e ( S , T ) > 0 e(S,T) > 0 e ( S , T ) > 0 and k k k with ∣ S ∣ , ∣ T ∣ ≤ k |S|,|T| \le k ∣ S ∣ , ∣ T ∣ ≤ k , there are S ′ ⊆ S S' \subseteq S S ′ ⊆ S and T ′ ⊆ T T' \subseteq T T ′ ⊆ T with e ( S ′ , T ′ ) ≥ e ( S , T ) / 2 e(S',T') \ge e(S,T)/2 e ( S ′ , T ′ ) ≥ e ( S , T ) /2 such that every vertex of S ′ S' S ′ has more than e ( S , T ) / ( 4 ∣ S ∣ ) e(S,T)/(4|S|) e ( S , T ) / ( 4∣ S ∣ ) neighbors in T ′ T' T ′ and every vertex of T ′ T' T ′ has more than e ( S , T ) / ( 4 ∣ T ∣ ) e(S,T)/(4|T|) e ( S , T ) / ( 4∣ T ∣ ) neighbors in S ′ S' S ′ .
From every starting vertex v ∈ S ′ ∪ ˙ T ′ v \in S' \mathbin{\dot\cup} T' v ∈ S ′ ∪ ˙ T ′ , the vectors of Andersen’s algorithm with parameter k k k satisfy ∥ x t A ∥ 2 ≥ ( d ( S , T ) / 16 ) ∥ x t ∥ 2 \lVert x_{t}A\rVert_{2} \ge(d(S,T)/16)\lVert x_{t}\rVert_{2} ∥ x t A ∥ 2 ≥ ( d ( S , T ) /16 ) ∥ x t ∥ 2 for some t < t 0 t < t_{0} t < t 0 . If d ( S , T ) < 16 d(S,T) < 16 d ( S , T ) < 16 , then also ∥ x 0 A ∥ 2 ≥ ∥ x 0 ∥ 2 \lVert x_{0}A\rVert_{2} \ge\lVert x_{0}\rVert_{2} ∥ x 0 A ∥ 2 ≥ ∥ x 0 ∥ 2 .
For d ( S , T ) ≥ 16 d(S,T) \ge16 d ( S , T ) ≥ 16 , we apply Andersen’s proof of Theorem 1 with λ = d ( S , T ) / 16 \lambda= d(S,T)/16 λ = d ( S , T ) /16 . For the last claim, every v ∈ S ′ ∪ ˙ T ′ v \in S' \mathbin{\dot\cup} T' v ∈ S ′ ∪ ˙ T ′ has a neighbor, so ∥ x 0 A ∥ 2 ≥ 1 = ∥ x 0 ∥ 2 \lVert x_0A\rVert_2 \ge1 = \lVert x_0\rVert_2 ∥ x 0 A ∥ 2 ≥ 1 = ∥ x 0 ∥ 2 .
Lemma C.3 (From growth to dense level sets [2 Lemma 1, weakened form] ). For a nonzero vector x ≥ 0 x \ge0 x ≥ 0 supported on one side and λ ≥ 1 \lambda\ge1 λ ≥ 1 with ∥ x A ∥ 2 ≥ λ ∥ x ∥ 2 \lVert xA\rVert_2 \ge\lambda\lVert x\rVert_2 ∥ x A ∥ 2 ≥ λ ∥ x ∥ 2 , there are nonempty dyadic level sets X X X of x / ∥ x ∥ 2 x/\lVert x\rVert_2 x / ∥ x ∥ 2 and Y Y Y of x A / ∥ x A ∥ 2 xA/\lVert xA\rVert_2 x A / ∥ x A ∥ 2 with d ( X , Y ) d(X,Y) d ( X , Y ) at least
λ 72 ( 1 + log 2 ( Δ / λ ) ) . (17) \frac{\lambda}{72\left(1+\log_2(\Delta/\lambda)\right)}. \tag*{(17)} 72 ( 1 + log 2 ( Δ/ λ ) ) λ . (17)
In Andersen’s Lemma 1, the density is at least λ / ( 72 + 16 log 2 ( Δ / λ ) ) \lambda/(72 + 16\log_2(\Delta/\lambda)) λ / ( 72 + 16 log 2 ( Δ/ λ )) for some level-set indices i , j i,j i , j satisfying ∣ i − j ∣ ≤ 4 + log 2 Δ |i-j| \le4+\log_2\Delta ∣ i − j ∣ ≤ 4 + log 2 Δ . Since λ ≤ Δ \lambda\le\Delta λ ≤ Δ , (18) is weaker, and we state it without the restriction on the level-set indices.
Neighbor-query implementation of Andersen’s algorithm
As in Andersen’s proof of Theorem 2 [2 ] , the iteration in Appendix § 9 .§ 1 has ∣ supp ( x t ) ∣ = O ( k 2 4 − t ) |\operatorname{supp}(x_t)| = O(k^{2^{4-t}}) ∣ supp ( x t ) ∣ = O ( k 2 4 − t ) . At step t t t , we read the adjacency list of each vertex u ∈ supp ( x t ) u \in\operatorname{supp}(x_t) u ∈ supp ( x t ) to its end, using deg ( u ) + 1 ≤ Δ + 1 \deg(u) + 1 \le\Delta+ 1 deg ( u ) + 1 ≤ Δ + 1 neighbor queries. Using the cached lists, we compute x t A x_tA x t A and e ( X , Y ) e(X,Y) e ( X , Y ) for all level sets X X X of x t / ∥ x t ∥ 2 x_t/\lVert x_t\rVert_2 x t / ∥ x t ∥ 2 and Y Y Y of x t A / ∥ x t A ∥ 2 x_tA/\lVert x_tA\rVert_2 x t A / ∥ x t A ∥ 2 without further queries. The total number of neighbor queries is therefore at most
( Δ + 1 ) ∑ t = 0 t 0 − 1 ∣ supp ( x t ) ∣ = O ( Δ k 2 ) , (\Delta+1)\sum_{t=0}^{t_0-1}|\operatorname{supp}(x_t)| = O(\Delta k^2), ( Δ + 1 ) t = 0 ∑ t 0 − 1 ∣ supp ( x t ) ∣ = O ( Δ k 2 ) ,
since Δ ≥ 1 \Delta\ge1 Δ ≥ 1 for a target of positive density. If Δ \Delta Δ is unknown, we omit the restriction ∣ i − j ∣ ≤ 4 + log 2 Δ |i-j| \le4+\log_2\Delta ∣ i − j ∣ ≤ 4 + log 2 Δ and consider all level sets X , Y X,Y X , Y with e ( X , Y ) > 0 e(X,Y)>0 e ( X , Y ) > 0 . No additional queries are needed, and the returned density is no smaller.
Logarithmic accumulation for weak-ℓ 2 \ell_2 ℓ 2
Andersen’s vectors are normalized in the Euclidean norm. For x ≥ 0 x \ge0 x ≥ 0 supported on L L L with ∥ x ∥ 2 ≤ 1 \lVert x\rVert_2 \le1 ∥ x ∥ 2 ≤ 1 , by Cauchy–Schwarz, I x ( i ) ≤ i I_x(i) \le\sqrt{i} I x ( i ) ≤ i for every i i i , that is, ∥ x ∥ 2 , ∞ ≤ 1 \lVert x\rVert_{2,\infty} \le1 ∥ x ∥ 2 , ∞ ≤ 1 in the notation of Definition 2.1 . We bound the prefix sums of y : = x A y := xA y := x A as in § 2.1 , for a prefix P m ( y ) P_m(y) P m ( y ) with d ( P i ( x ) , P m ( y ) ) ≤ σ d(P_i(x),P_m(y)) \le\sigma d ( P i ( x ) , P m ( y )) ≤ σ for every prefix P i ( x ) P_i(x) P i ( x ) of x x x .
We also assume that every vertex in supp ( x ) \operatorname{supp}(x) supp ( x ) has degree below σ 2 \sigma^2 σ 2 , as in Search p \operatorname{Search}_p Search p after the adjacency lists of supp ( x ) \operatorname{supp}(x) supp ( x ) have been read and no star has been returned (Lemma A.6(a)). By the density assumption, and since the vertices of P i ( x ) P_i(x) P i ( x ) have degree below σ 2 \sigma^2 σ 2 and those of P m ( y ) P_m(y) P m ( y ) degree at most Δ \Delta Δ , e ( P i ( x ) , P m ( y ) ) ≤ g ( i ) e(P_i(x),P_m(y)) \le g(i) e ( P i ( x ) , P m ( y )) ≤ g ( i ) for g ( i ) : = min { σ 2 i , σ i m , Δ m } g(i) := \min\{\sigma^2i,\sigma\sqrt{im},\Delta m\} g ( i ) := min { σ 2 i , σ im , Δ m } . We write r 0 : = m / σ 2 r_0 := m/\sigma^2 r 0 := m / σ 2 and r 1 : = Δ 2 m / σ 2 r_1 := \Delta^2m/\sigma^2 r 1 := Δ 2 m / σ 2 . Since y ≠ 0 y \ne0 y = 0 , Δ ≥ 1 \Delta\ge1 Δ ≥ 1 and r 1 / r 0 = Δ 2 ≥ 1 r_1/r_0 = \Delta^2 \ge1 r 1 / r 0 = Δ 2 ≥ 1 . The degree bound σ 2 i \sigma^2i σ 2 i is the smallest of the three for i ≤ r 0 i \le r_0 i ≤ r 0 , the density bound σ i m \sigma\sqrt{im} σ im for r 0 ≤ i ≤ r 1 r_0 \le i \le r_1 r 0 ≤ i ≤ r 1 , and the maximum-degree bound Δ m \Delta m Δ m for i ≥ r 1 i \ge r_1 i ≥ r 1 . By summation by parts, as in the proof of Proposition A.4 ,
I y ( m ) ≤ ∑ i = 1 ℓ x ( i ) ( g ( i ) − g ( i − 1 ) ) . I_y(m) \le\sum_{i=1}^{\ell} x_{(i)}\bigl(g(i)-g(i-1)\bigr). I y ( m ) ≤ i = 1 ∑ ℓ x ( i ) ( g ( i ) − g ( i − 1 ) ) .
We split this sum at r 0 r_0 r 0 and r 1 r_1 r 1 and bound the three parts separately. The terms with i ≤ r 0 i \le r_0 i ≤ r 0 have g ( i ) − g ( i − 1 ) = σ 2 g(i)-g(i-1)=\sigma^2 g ( i ) − g ( i − 1 ) = σ 2 , so their total contribution is at most σ 2 I x ( r 0 ) ≤ σ 2 r 0 = σ m \sigma^2 I_x(r_0) \le\sigma^2\sqrt{r_0} = \sigma\sqrt{m} σ 2 I x ( r 0 ) ≤ σ 2 r 0 = σ m . The terms with i ≥ r 1 + 1 i \ge r_1+1 i ≥ r 1 + 1 are zero, since g ( i ) = g ( i − 1 ) = Δ m g(i)=g(i-1)=\Delta m g ( i ) = g ( i − 1 ) = Δ m . If i − 1 < r 0 < i i-1<r_0<i i − 1 < r 0 < i or i − 1 < r 1 < i i-1<r_1<i i − 1 < r 1 < i , the corresponding term is at most x ( i ) g ( i ) ≤ σ m x_{(i)}g(i)\le\sigma\sqrt{m} x ( i ) g ( i ) ≤ σ m . There are at most two such indices. For the remaining indices, r 0 ≤ i − 1 < i ≤ r 1 r_0 \le i-1 < i \le r_1 r 0 ≤ i − 1 < i ≤ r 1 , so g ( i ) − g ( i − 1 ) = σ m ( i − i − 1 ) ≤ σ m / i g(i)-g(i-1)=\sigma\sqrt{m}(\sqrt{i}-\sqrt{i-1}) \le\sigma\sqrt{m}/\sqrt{i} g ( i ) − g ( i − 1 ) = σ m ( i − i − 1 ) ≤ σ m / i . Since x ( i ) ≤ I x ( i ) / i ≤ 1 / i x_{(i)} \le I_x(i)/i \le1/\sqrt{i} x ( i ) ≤ I x ( i ) / i ≤ 1/ i , the terms in a dyadic range 2 j ≤ i < 2 j + 1 2^j \le i < 2^{j+1} 2 j ≤ i < 2 j + 1 therefore add up to
∑ 2 j ≤ i < 2 j + 1 r 0 ≤ i − 1 < i ≤ r 1 x ( i ) ( g ( i ) − g ( i − 1 ) ) = O ( σ m ) ∑ 2 j ≤ i < 2 j + 1 1 i = O ( σ m ) . \sum_{\substack{2^j\le i<2^{j+1}\\r_0\le i-1<i\le r_1}}x_{(i)}(g(i)-g(i-1))=O(\sigma\sqrt{m})\sum_{2^j\le i<2^{j+1}}\frac{1}{i}=O(\sigma\sqrt{m}). 2 j ≤ i < 2 j + 1 r 0 ≤ i − 1 < i ≤ r 1 ∑ x ( i ) ( g ( i ) − g ( i − 1 )) = O ( σ m ) 2 j ≤ i < 2 j + 1 ∑ i 1 = O ( σ m ) .
Since r 1 / r 0 = Δ 2 r_1/r_0=\Delta^2 r 1 / r 0 = Δ 2 , at most 2 log 2 Δ + O ( 1 ) 2\log_2\Delta+O(1) 2 log 2 Δ + O ( 1 ) dyadic ranges contain these remaining indices. Altogether,
I y ( m ) = O ( σ m ( 1 + log 2 Δ ) ) . (18) I_y(m)=O(\sigma\sqrt{m}(1+\log_2\Delta)). \tag*{(18)} I y ( m ) = O ( σ m ( 1 + log 2 Δ )) . (18)
Using only I x ( i ) ≤ i I_x(i)\le\sqrt{i} I x ( i ) ≤ i , we cannot improve the logarithmic dependence in the preceding upper bound on ∑ i x ( i ) ( g ( i ) − g ( i − 1 ) ) \sum_i x_{(i)}(g(i)-g(i-1)) ∑ i x ( i ) ( g ( i ) − g ( i − 1 )) . The vector x x x with x ( i ) : = i − i − 1 x_{(i)}:=\sqrt{i}-\sqrt{i-1} x ( i ) := i − i − 1 for i ≤ ℓ i\le\ell i ≤ ℓ , where ℓ > r 1 \ell>r_1 ℓ > r 1 and m ≥ σ 2 m\ge\sigma^2 m ≥ σ 2 , satisfies I x ( i ) = i I_x(i)=\sqrt{i} I x ( i ) = i , and the contribution to this sum from each dyadic range between r 0 r_0 r 0 and r 1 r_1 r 1 is Θ ( σ m ) \Theta(\sigma\sqrt{m}) Θ ( σ m ) . This vector has ∥ x ∥ 2 > 1 \lVert x\rVert_2>1 ∥ x ∥ 2 > 1 . For ∥ x ∥ 2 ≤ 1 \lVert x\rVert_2\le1 ∥ x ∥ 2 ≤ 1 , however, the sum is O ( σ m 1 + log 2 Δ ) O(\sigma\sqrt{m}\sqrt{1+\log_2\Delta}) O ( σ m 1 + log 2 Δ ) : by Cauchy–Schwarz, it is at most ∥ x ∥ 2 ( ∑ i ( g ( i ) − g ( i − 1 ) ) 2 ) 1 / 2 \lVert x\rVert_2(\sum_i(g(i)-g(i-1))^2)^{1/2} ∥ x ∥ 2 ( ∑ i ( g ( i ) − g ( i − 1 ) ) 2 ) 1/2 , and ( g ( i ) − g ( i − 1 ) ) 2 = ( ∫ i − 1 i g ′ ( s ) d s ) 2 ≤ ∫ i − 1 i g ′ ( s ) 2 d s (g(i)-g(i-1))^2=(\int_{i-1}^{i}g'(s)\,ds)^2\le\int_{i-1}^{i}g'(s)^2\,ds ( g ( i ) − g ( i − 1 ) ) 2 = ( ∫ i − 1 i g ′ ( s ) d s ) 2 ≤ ∫ i − 1 i g ′ ( s ) 2 d s , so that
∑ i ( g ( i ) − g ( i − 1 ) ) 2 ≤ ∫ 0 ∞ g ′ ( s ) 2 d s = σ 4 r 0 + σ 2 m 4 ln r 1 r 0 = σ 2 m ( 1 + 1 2 ln Δ ) . \sum_i(g(i)-g(i-1))^2\le\int_0^\infty g'(s)^2\,ds=\sigma^4r_0+\frac{\sigma^2m}{4}\ln\frac{r_1}{r_0}=\sigma^2m\left(1+\frac{1}{2}\ln\Delta\right). i ∑ ( g ( i ) − g ( i − 1 ) ) 2 ≤ ∫ 0 ∞ g ′ ( s ) 2 d s = σ 4 r 0 + 4 σ 2 m ln r 0 r 1 = σ 2 m ( 1 + 2 1 ln Δ ) .
To bound the prefix sums of y A yA y A by Cauchy–Schwarz, we need an upper bound on ∥ y ∥ 2 \lVert y\rVert_2 ∥ y ∥ 2 . We have bounded only ∥ y ∥ 2 , ∞ \lVert y\rVert_{2,\infty} ∥ y ∥ 2 , ∞ . For p > 2 p>2 p > 2 , by contrast, we can bound ∥ y ∥ p , ∞ \lVert y\rVert_{p,\infty} ∥ y ∥ p , ∞ in terms of ∥ x ∥ p , ∞ \lVert x\rVert_{p,\infty} ∥ x ∥ p , ∞ (Proposition A.4 ).
The logarithm in Andersen’s Lemma 1 also comes from a sum over logarithmically many scales: in its proof, he sums over all level-set indices i , j i,j i , j with ∣ i − j ∣ ≤ 4 + log 2 ( Δ / λ ) |i-j|\le4+\log_2(\Delta/\lambda) ∣ i − j ∣ ≤ 4 + log 2 ( Δ/ λ ) . For p > 2 p>2 p > 2 , in contrast, x ( i ) ≤ ∥ x ∥ p , ∞ i − 1 / p x_{(i)}\le\lVert x\rVert_{p,\infty}i^{-1/p} x ( i ) ≤ ∥ x ∥ p , ∞ i − 1/ p . The sum over the dyadic range 2 j ≤ i < 2 j + 1 2^j\le i<2^{j+1} 2 j ≤ i < 2 j + 1 is then O ( m ∥ x ∥ p , ∞ 2 j ( 1 / 2 − 1 / p ) ) O(\sqrt{m}\lVert x\rVert_{p,\infty}2^{j(1/2-1/p)}) O ( m ∥ x ∥ p , ∞ 2 j ( 1/2 − 1/ p ) ) . The sum over all ranges is therefore O p ( 1 ) O_p(1) O p ( 1 ) times the largest of these bounds, and there is no logarithmic factor in Proposition A.4 .
For nonnegative matrices, the logarithmic factor in (18) is necessary (see Bilu and Linial [8 ] ). For a nonnegative matrix B B B and nonempty sets S , T S,T S , T of row and column indices, we write
d B ( S , T ) : = ∑ u ∈ S ∑ w ∈ T B u w ∣ S ∣ ∣ T ∣ . d_B(S,T):=\frac{\sum_{u\in S}\sum_{w\in T}B_{uw}}{\sqrt{|S||T|}}. d B ( S , T ) := ∣ S ∣∣ T ∣ ∑ u ∈ S ∑ w ∈ T B u w .
In Construction C.4, we define a symmetric matrix A ˉ \bar{A} A ˉ and a vector ξ L \xi_L ξ L with ∥ ξ L A ˉ ∥ 2 = λ ∥ ξ L ∥ 2 \lVert\xi_L\bar{A}\rVert_2=\lambda\lVert\xi_L\rVert_2 ∥ ξ L A ˉ ∥ 2 = λ ∥ ξ L ∥ 2 such that d A ˉ ( S , T ) = O ( λ / log 2 Δ ) d_{\bar{A}}(S,T)=O(\lambda/\log_2\Delta) d A ˉ ( S , T ) = O ( λ / log 2 Δ ) for all nonempty S ⊆ L S\subseteq L S ⊆ L and T ⊆ R T\subseteq R T ⊆ R , where Δ \Delta Δ is the largest row sum.
Construction C.4. For an integer ν ≥ 1 \nu\ge1 ν ≥ 1 and ζ : = 2 ν \zeta:=2^\nu ζ := 2 ν , the sets L L L and R R R are partitioned into blocks L i , R i L_i,R_i L i , R i of size 4 i 4^i 4 i for i = 0 , … , ν − 1 i=0,\ldots,\nu-1 i = 0 , … , ν − 1 . The symmetric matrix A ˉ \bar{A} A ˉ , indexed by L ∪ ˙ R L\mathbin{\dot\cup}R L ∪ ˙ R , has entry ζ 2 − i − j \zeta2^{-i-j} ζ 2 − i − j between L i L_i L i and R j R_j R j and zero entries on L × L L\times L L × L and R × R R\times R R × R . The vector ξ L \xi_L ξ L equals 2 − i 2^{-i} 2 − i on L i L_i L i and zero on R R R , the vector ξ R \xi_R ξ R is defined symmetrically, and λ : = ∥ ξ L A ˉ ∥ 2 / ∥ ξ L ∥ 2 \lambda:=\lVert\xi_L\bar{A}\rVert_2/\lVert\xi_L\rVert_2 λ := ∥ ξ L A ˉ ∥ 2 / ∥ ξ L ∥ 2 .
Proposition C.5. The matrix of Construction C.4 has spectral radius ν ζ \nu\zeta ν ζ and largest row sum Δ = ζ ( ζ − 1 ) \Delta=\zeta(\zeta-1) Δ = ζ ( ζ − 1 ) . Moreover,
λ = ν ζ , ζ ≤ max ∅ ≠ S ⊆ L ∅ ≠ T ⊆ R d A ˉ ( S , T ) ≤ 9 ζ . \lambda=\nu\zeta,\qquad\zeta\le\max_{\varnothing\ne S\subseteq L\atop\varnothing\ne T\subseteq R}d_{\bar{A}}(S,T)\le9\zeta. λ = ν ζ , ζ ≤ ∅ = T ⊆ R ∅ = S ⊆ L max d A ˉ ( S , T ) ≤ 9 ζ .
The nonempty dyadic level sets of ξ L / ∥ ξ L ∥ 2 \xi_L/\lVert\xi_L\rVert_2 ξ L / ∥ ξ L ∥ 2 and ξ L A ˉ / ∥ ξ L A ˉ ∥ 2 \xi_{L\bar{A}}/\lVert\xi_{L\bar{A}}\rVert_2 ξ L A ˉ / ∥ ξ L A ˉ ∥ 2 are L 0 , … , L ν − 1 L_0,\ldots,L_{\nu-1} L 0 , … , L ν − 1 and R 0 , … , R ν − 1 R_0,\ldots,R_{\nu-1} R 0 , … , R ν − 1 , respectively. Every block density d A ˉ ( L i , R j ) d_{\bar{A}}(L_i,R_j) d A ˉ ( L i , R j ) equals ζ \zeta ζ . The ratio of λ \lambda λ to the maximum of d A ˉ ( S , T ) d_{\bar{A}}(S,T) d A ˉ ( S , T ) over nonempty S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R is Θ ( ν ) = Θ ( log 2 Δ ) \Theta(\nu)=\Theta(\log_2\Delta) Θ ( ν ) = Θ ( log 2 Δ ) . The right-hand side of (17) , evaluated at λ = ν ζ \lambda=\nu\zeta λ = ν ζ , is Θ ( ζ ) \Theta(\zeta) Θ ( ζ ) .
Proof. For u ∈ R j u \in R_j u ∈ R j with 0 ≤ j < ν 0 \leq j < \nu 0 ≤ j < ν , the contribution from each left block L i L_i L i to ( ξ L A ˉ ) ( u ) (\xi_{L\bar{A}})(u) ( ξ L A ˉ ) ( u ) is 4 i ⋅ 2 − i − j ⋅ ( ζ 2 − i − j ) = ζ 2 − j 4^i \cdot2^{-i-j}\cdot(\zeta2^{-i-j})=\zeta2^{-j} 4 i ⋅ 2 − i − j ⋅ ( ζ 2 − i − j ) = ζ 2 − j , so
( ξ L A ˉ ) ( u ) = ν ζ 2 − j = ν ζ ξ R ( u ) . (\xi_{L\bar{A}})(u)=\nu\zeta2^{-j}=\nu\zeta\xi_R(u). ( ξ L A ˉ ) ( u ) = ν ζ 2 − j = ν ζ ξ R ( u ) .
By symmetry, ξ R A ˉ = ν ζ ξ L \xi_{R\bar{A}}=\nu\zeta\xi_L ξ R A ˉ = ν ζ ξ L , so ξ L + ξ R \xi_L+\xi_R ξ L + ξ R is a positive eigenvector with eigenvalue ν ζ \nu\zeta ν ζ , which is therefore the spectral radius. Since ∥ ξ L ∥ 2 = ∥ ξ R ∥ 2 = ν \lVert\xi_L\rVert_2=\lVert\xi_R\rVert_2=\sqrt{\nu} ∥ ξ L ∥ 2 = ∥ ξ R ∥ 2 = ν , λ = ν ζ \lambda=\nu\zeta λ = ν ζ . By direct summation, the largest row sum is Δ = ζ ( ζ − 1 ) \Delta=\zeta(\zeta-1) Δ = ζ ( ζ − 1 ) , and d A ˉ ( L i , R j ) = ζ d_{\bar{A}}(L_i,R_j)=\zeta d A ˉ ( L i , R j ) = ζ for all i , j i,j i , j . Consecutive block values differ by a factor of two, so the nonempty dyadic level sets are exactly the blocks.
For nonempty S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R , we write s i : = ∣ S ∩ L i ∣ s_i:=|S\cap L_i| s i := ∣ S ∩ L i ∣ and take the integer q ≥ 0 q\geq0 q ≥ 0 with ∣ S ∣ ≤ 2 q < 2 ∣ S ∣ \sqrt{|S|}\leq2^q<2\sqrt{|S|} ∣ S ∣ ≤ 2 q < 2 ∣ S ∣ . Since s i ≤ 4 i s_i\leq4^i s i ≤ 4 i ,
∑ i = 0 ν − 1 s i 2 − i ≤ ∑ i = 0 q − 1 2 i + 2 − q ∣ S ∣ ≤ 2 q + ∣ S ∣ 2 − q ≤ 3 ∣ S ∣ . \sum_{i=0}^{\nu-1}s_i2^{-i}\leq\sum_{i=0}^{q-1}2^i+2^{-q}|S|\leq2^q+|S|2^{-q}\leq3\sqrt{|S|}. i = 0 ∑ ν − 1 s i 2 − i ≤ i = 0 ∑ q − 1 2 i + 2 − q ∣ S ∣ ≤ 2 q + ∣ S ∣ 2 − q ≤ 3 ∣ S ∣ .
We apply the same bound to t j : = ∣ T ∩ R j ∣ t_j:=|T\cap R_j| t j := ∣ T ∩ R j ∣ and obtain
∑ u ∈ S ∑ w ∈ T A ˉ u w = ζ ( ∑ i = 0 ν − 1 s i 2 − i ) ( ∑ j = 0 ν − 1 t j 2 − j ) ≤ 9 ζ ∣ S ∣ ∣ T ∣ . \sum_{u\in S}\sum_{w\in T}\bar{A}_{uw}
=\zeta\left(\sum_{i=0}^{\nu-1}s_i2^{-i}\right)\left(\sum_{j=0}^{\nu-1}t_j2^{-j}\right)
\leq9\zeta\sqrt{|S||T|}. u ∈ S ∑ w ∈ T ∑ A ˉ u w = ζ ( i = 0 ∑ ν − 1 s i 2 − i ) ( j = 0 ∑ ν − 1 t j 2 − j ) ≤ 9 ζ ∣ S ∣∣ T ∣ .
Finally, since Δ = ζ ( ζ − 1 ) \Delta=\zeta(\zeta-1) Δ = ζ ( ζ − 1 ) and λ = ν ζ \lambda=\nu\zeta λ = ν ζ , both log 2 Δ \log_2\Delta log 2 Δ and 1 + log 2 ( Δ / λ ) 1+\log_2(\Delta/\lambda) 1 + log 2 ( Δ/ λ ) are Θ ( ν ) \Theta(\nu) Θ ( ν ) , so the right-hand side of (17) is Θ ( ζ ) \Theta(\zeta) Θ ( ζ ) .
Lower bounds
Since sets X , Y X,Y X , Y with d ( X , Y ) = Ω ( k ) d(X,Y)=\Omega(k) d ( X , Y ) = Ω ( k ) have Ω ( k 2 ) \Omega(k^2) Ω ( k 2 ) edges between them, an output of o ( k 2 ) o(k^2) o ( k 2 ) vertices per side must have many more edges than vertices, as the target does, and the algorithm has to find these edges. The query lower bound is proved by hiding a complete bipartite graph at uniformly chosen adjacency-list positions (Appendix § 10 .§ 1 ), and the computational lower bounds by reducing Densest k k k -Subgraph to the local problem (Appendix § 10 .§ 2 ).
Definition D.1. An algorithm A A A receives a starting vertex v v v , an integer k ≥ 1 k\geq1 k ≥ 1 , and neighbor-query access to a simple bipartite graph G G G , as specified in the graph-access model of Appendix § 8 .§ 2 . The algorithm has output bound ϕ \phi ϕ if, for every input, it returns either ⊥ \bot ⊥ or nonempty sets X ⊆ L X\subseteq L X ⊆ L , Y ⊆ R Y\subseteq R Y ⊆ R with ∣ X ∣ , ∣ Y ∣ ≤ ϕ ( k ) |X|,|Y|\leq\phi(k) ∣ X ∣ , ∣ Y ∣ ≤ ϕ ( k ) . Unless we explicitly allow randomness, algorithms are deterministic; for randomized algorithms, all output, query, and running-time bounds hold for every choice of the internal randomness, and success probabilities are over that randomness. Unless we impose a running-time bound, computation between queries is unrestricted.
The query lower bound
Theorem D.2 (Queries sublinear in Δ \Delta Δ ). For a constant 0 < ρ ≤ 1 0<\rho\leq1 0 < ρ ≤ 1 and ϕ ( k ) = o ( k 2 ) \phi(k)=o(k^2) ϕ ( k ) = o ( k 2 ) , if a possibly randomized algorithm A A A as in Definition D.1 has output bound ϕ \phi ϕ and makes at most q ( k , Δ ) q(k,\Delta) q ( k , Δ ) queries on every input, where q ( k , Δ ) = o ( Δ ) q(k,\Delta)=o(\Delta) q ( k , Δ ) = o ( Δ ) as Δ → ∞ \Delta\to\infty Δ → ∞ for every fixed k k k , then, for every sufficiently large k k k , there is a simple bipartite graph G G G containing a complete bipartite subgraph with sides S ⊆ L S\subseteq L S ⊆ L and T ⊆ R T\subseteq R T ⊆ R of k k k vertices each, such that from every v ∈ S ∪ T v\in S\cup T v ∈ S ∪ T the output of A A A is ⊥ \bot ⊥ or has density below ρ k \rho k ρ k with probability at least $2/3.
Proof of Theorem D.2 . For the extension to randomized algorithms, we use a transcript-coupling approach inspired by Peng et al. [32 ] . Since ϕ ( k ) = o ( k 2 ) \phi(k)=o(k^2) ϕ ( k ) = o ( k 2 ) , we can fix any sufficiently large k k k with 2 ϕ ( k ) < ρ k \sqrt{2\phi(k)}<\rho k 2 ϕ ( k ) < ρ k . Choose integers N > k N>k N > k and then Δ ≥ k \Delta\ge k Δ ≥ k so that
2 k 2 q ( k , Δ ) Δ + 4 ϕ ( k ) k 2 N − 1 < 1 3 . \frac{2k^2q(k,\Delta)}{\Delta}+\frac{4\phi(k)k^2}{N-1}<\frac{1}{3}. Δ 2 k 2 q ( k , Δ ) + N − 1 4 ϕ ( k ) k 2 < 3 1 .
which is possible because q ( k , Δ ) = o ( Δ ) q(k,\Delta)=o(\Delta) q ( k , Δ ) = o ( Δ ) for fixed k k k . Let G 0 G_0 G 0 consist of N N N disjoint stars centered on each side, each with Δ \Delta Δ leaves, with fixed vertex identifiers and adjacency-list orders. Choose S S S and T T T independently and uniformly among the k k k -subsets of the left and right centers, respectively. For each chosen center, independently select k k k of the Δ \Delta Δ positions in its adjacency list uniformly, and replace the entries at those positions by the k k k target centers on the opposite side in identifier order. Isolate the corresponding leaves, keeping all vertex identifiers. The resulting graph G G G is simple and bipartite, every center still has degree Δ \Delta Δ , and S , T S,T S , T span a complete bipartite subgraph of density k k k .
Fix a center v v v and condition on v ∈ S ∪ ˙ T v\in S\mathbin{\dot\cup}T v ∈ S ∪ ˙ T . Fix the internal randomness of A independently of the construction, and compare its runs from v v v on G 0 G_0 G 0 and G G G using this same randomness. The run on G 0 G_0 G 0 is independent of the chosen target and positions. Each query in that run concerns at most one original star edge, either through its position in a center’s list or through a query at its leaf. Conditional on v ∈ S ∪ ˙ T v\in S\mathbin{\dot\cup}T v ∈ S ∪ ˙ T , each such edge is replaced with probability at most k / Δ k/\Delta k /Δ . Until a differing answer is received, the two computations coincide. By a union bound over the at most q ( k , Δ ) q(k,\Delta) q ( k , Δ ) queries on G 0 G_0 G 0 , the probability of any differing answer is at most k q ( k , Δ ) / Δ kq(k,\Delta)/\Delta k q ( k , Δ ) /Δ .
The output on G 0 G_0 G 0 contains at most 2 ϕ ( k ) 2\phi(k) 2 ϕ ( k ) centers. Each center other than v v v belongs to S ∪ ˙ T S\mathbin{\dot\cup}T S ∪ ˙ T with conditional probability at most k / ( N − 1 ) k/(N-1) k / ( N − 1 ) , so the probability that the output contains another target center is at most 2 ϕ ( k ) k / ( N − 1 ) 2\phi(k)k/(N-1) 2 ϕ ( k ) k / ( N − 1 ) . If neither event occurs, the output on G G G is the same as on G 0 G_0 G 0 and contains no edge of S × T S\times T S × T . If it is a pair ( X , Y ) (X,Y) ( X , Y ) rather than ⊥ \perp ⊥ , all its edges belong to G 0 G_0 G 0 . Writing e 0 : = e G 0 ( X , Y ) e_0:=e_{G_0}(X,Y) e 0 := e G 0 ( X , Y ) , we have e 0 ≤ ∣ X ∣ + ∣ Y ∣ ≤ 2 ϕ ( k ) e_0\le|X|+|Y|\le2\phi(k) e 0 ≤ ∣ X ∣ + ∣ Y ∣ ≤ 2 ϕ ( k ) since G 0 G_0 G 0 is a forest, and e 0 ≤ ∣ X ∣ ∣ Y ∣ e_0\le|X||Y| e 0 ≤ ∣ X ∣∣ Y ∣ . Thus
d G ( X , Y ) ≤ e 0 ∣ X ∣ ∣ Y ∣ ≤ e 0 ≤ 2 ϕ ( k ) < ρ k . d_G(X,Y)\le\frac{e_0}{\sqrt{|X||Y|}}\le\sqrt{e_0}\le\sqrt{2\phi(k)}<\rho k. d G ( X , Y ) ≤ ∣ X ∣∣ Y ∣ e 0 ≤ e 0 ≤ 2 ϕ ( k ) < ρ k .
Let p v ( G ) p_v(G) p v ( G ) be the probability, over the internal randomness of A, of returning sets of density at least ρ k \rho k ρ k from v v v on G G G . Averaging also over that randomness in the preceding bounds, we obtain
E [ p v ( G ) ∣ v ∈ S ∪ ˙ T ] ≤ k q ( k , Δ ) Δ + 2 ϕ ( k ) k N − 1 , \mathbb{E}[p_v(G)\mid v\in S\mathbin{\dot\cup}T]\le\frac{kq(k,\Delta)}{\Delta}+\frac{2\phi(k)k}{N-1}, E [ p v ( G ) ∣ v ∈ S ∪ ˙ T ] ≤ Δ k q ( k , Δ ) + N − 1 2 ϕ ( k ) k ,
where the expectation is over the random construction. There are 2 N 2N 2 N centers, each belonging to S ∪ ˙ T S\mathbin{\dot\cup}T S ∪ ˙ T with probability k / N k/N k / N , so
E [ ∑ v ∈ S ∪ ˙ T p v ( G ) ] ≤ 2 k 2 q ( k , Δ ) Δ + 4 ϕ ( k ) k 2 N − 1 < 1 3 . \mathbb{E}\left[\sum_{v\in S\mathbin{\dot\cup}T}p_v(G)\right]\le\frac{2k^2q(k,\Delta)}{\Delta}+\frac{4\phi(k)k^2}{N-1}<\frac{1}{3}. E [ v ∈ S ∪ ˙ T ∑ p v ( G ) ] ≤ Δ 2 k 2 q ( k , Δ ) + N − 1 4 ϕ ( k ) k 2 < 3 1 .
Hence there is one fixed graph and target for which this sum is below 1 / 3 1/3 1/3 . Every summand is nonnegative, so p v ( G ) < 1 / 3 p_v(G)<1/3 p v ( G ) < 1/3 for every v ∈ S ∪ ˙ T v\in S\mathbin{\dot\cup}T v ∈ S ∪ ˙ T , as required. □ \square □
Corollary D.3 (Approximation and output size with restricted queries). For α ( k ) ≥ 1 \alpha(k)\ge1 α ( k ) ≥ 1 with α ( k ) = o ( k ) \alpha(k)=o(k) α ( k ) = o ( k ) and ϕ ( k ) = o ( k 2 / α ( k ) 2 ) \phi(k)=o(k^2/\alpha(k)^2) ϕ ( k ) = o ( k 2 / α ( k ) 2 ) , if a possibly randomized algorithm as in Definition D.1 has output bound ϕ \phi ϕ and makes at most q ( k , Δ ) q(k,\Delta) q ( k , Δ ) queries, where q ( k , Δ ) = o ( Δ ) q(k,\Delta)=o(\Delta) q ( k , Δ ) = o ( Δ ) as Δ → ∞ \Delta\to\infty Δ → ∞ for every fixed k k k , then, for every sufficiently large k k k , there is a simple bipartite graph containing a complete bipartite subgraph with sides S , T S,T S , T of k k k vertices each, such that, from every v ∈ S ∪ ˙ T v\in S\mathbin{\dot\cup}T v ∈ S ∪ ˙ T , the algorithm returns ⊥ \perp ⊥ or sets of density below d ( S , T ) / α ( k ) d(S,T)/\alpha(k) d ( S , T ) / α ( k ) with probability at least 2 / 3 2/3 2/3 .
Proof. We apply the construction in the proof of Theorem D.2 with ρ = 1 / α ( k ) \rho= 1/\alpha(k) ρ = 1/ α ( k ) , since its condition 2 ϕ ( k ) < ρ k \sqrt{2\phi(k)} < \rho k 2 ϕ ( k ) < ρ k holds for all sufficiently large k k k :
α ( k ) k 2 ϕ ( k ) = 2 α ( k ) 2 ϕ ( k ) k 2 < 1 , \frac{\alpha(k)}{k}\sqrt{2\phi(k)} = \sqrt{\frac{2\alpha(k)^2\phi(k)}{k^2}} < 1, k α ( k ) 2 ϕ ( k ) = k 2 2 α ( k ) 2 ϕ ( k ) < 1 ,
as the expression tends to zero. For each such k k k , choose N N N and Δ \Delta Δ as in that proof. From every target vertex of the resulting fixed graph, the algorithm returns ⊥ \perp ⊥ or sets of density below k / α ( k ) = d ( S , T ) / α ( k ) k/\alpha(k) = d(S,T)/\alpha(k) k / α ( k ) = d ( S , T ) / α ( k ) with probability at least 2 / 3 2/3 2/3 .
Computational lower bounds
For both lower bounds under SPCH and ETH, we use the same reduction. In Appendix § 10 .§ 2.1 , we construct a dense subgraph on k k k vertices of a graph J J J from the outputs of a local algorithm on its bipartite double cover, and in Appendices § 10 .§ 2.2 and § 10 .§ 2.3 , we prove the two lower bounds. Polynomial time means time polynomial in the number of vertices of the input graph, uniformly over all k k k up to that number.
Reduction from Densest k k k -Subgraph
For a simple graph J J J on N N N vertices, e J ( U ) e_J(U) e J ( U ) is the number of edges induced by U ⊆ V ( J ) U \subseteq V(J) U ⊆ V ( J ) , and the bipartite double cover G G G of J J J has two copies L , R L, R L , R of V ( J ) V(J) V ( J ) and edges u L w R , w L u R u_Lw_R, w_Lu_R u L w R , w L u R for every u w ∈ E ( J ) uw \in E(J) u w ∈ E ( J ) . The graph G G G has 2 N 2N 2 N vertices, and each vertex of G G G has the same degree as the corresponding vertex of J J J , which is below N N N . For k ≥ 2 k \ge2 k ≥ 2 , the two copies S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R of a k k k -clique in J J J are cohesive with d ( S , T ) = k − 1 d(S,T) = k - 1 d ( S , T ) = k − 1 , since every vertex has k − 1 k - 1 k − 1 neighbors in the opposite set.
Lemma D.4 (Extracting a dense k k k -vertex subgraph). For a simple graph J J J on at least k ≥ 2 k \ge2 k ≥ 2 vertices and its bipartite double cover G G G , 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 , B ≥ 1 B \ge1 B ≥ 1 , and nonempty sets X ⊆ L X \subseteq L X ⊆ L and Y ⊆ R Y \subseteq R Y ⊆ R with ∣ X ∣ , ∣ Y ∣ ≤ B k |X|, |Y| \le Bk ∣ X ∣ , ∣ Y ∣ ≤ B k and d ( X , Y ) ≥ ρ ( k − 1 ) d(X,Y) \ge\rho(k - 1) d ( X , Y ) ≥ ρ ( k − 1 ) , a set U U U of k k k vertices of J J J can be found in polynomial time with
e J ( U ) ≥ ρ 2 16 B ( k 2 ) . e_J(U) \ge\frac{\rho^2}{16B}\binom{k}{2}. e J ( U ) ≥ 16 B ρ 2 ( 2 k ) .
Proof. For h : = ⌊ k / 2 ⌋ h := \lfloor k/2 \rfloor h := ⌊ k /2 ⌋ , we take X ′ X' X ′ to be the min { ∣ X ∣ , h } \min\{|X|, h\} min { ∣ X ∣ , h } vertices of X X X with the most neighbors in Y Y Y , and Y ′ Y' Y ′ the min { ∣ Y ∣ , h } \min\{|Y|, h\} min { ∣ Y ∣ , h } vertices of Y Y Y with the most neighbors in X ′ X' X ′ .
Since ∣ X ′ ∣ + ∣ Y ′ ∣ ≤ 2 h ≤ k |X'| + |Y'| \le2h \le k ∣ X ′ ∣ + ∣ Y ′ ∣ ≤ 2 h ≤ k , we form U U U from the corresponding vertices of J J J , adding arbitrary vertices until ∣ U ∣ = k |U| = k ∣ U ∣ = k . Each edge of J J J has at most two copies in the double cover, so e J ( U ) ≥ e ( X ′ , Y ′ ) / 2 e_J(U) \ge e(X',Y')/2 e J ( U ) ≥ e ( X ′ , Y ′ ) /2 .
The vertices of X ′ X' X ′ have average degree into Y Y Y at least e ( X , Y ) / ∣ X ∣ e(X,Y)/|X| e ( X , Y ) /∣ X ∣ , so e ( X ′ , Y ) ≥ ( ∣ X ′ ∣ / ∣ X ∣ ) e ( X , Y ) e(X',Y) \ge(|X'|/|X|)e(X,Y) e ( X ′ , Y ) ≥ ( ∣ X ′ ∣/∣ X ∣ ) e ( X , Y ) , and similarly e ( X ′ , Y ′ ) ≥ ( ∣ Y ′ ∣ / ∣ Y ∣ ) e ( X ′ , Y ) e(X',Y') \ge(|Y'|/|Y|)e(X',Y) e ( X ′ , Y ′ ) ≥ ( ∣ Y ′ ∣/∣ Y ∣ ) e ( X ′ , Y ) . Therefore,
e ( X ′ , Y ′ ) ≥ ∣ X ′ ∣ ∣ Y ′ ∣ ∣ X ∣ ∣ Y ∣ e ( X , Y ) = h 2 e ( X , Y ) max { ∣ X ∣ , h } max { ∣ Y ∣ , h } . e(X',Y') \ge\frac{|X'||Y'|}{|X||Y|}e(X,Y) = \frac{h^2e(X,Y)}{\max\{|X|,h\}\max\{|Y|,h\}}. e ( X ′ , Y ′ ) ≥ ∣ X ∣∣ Y ∣ ∣ X ′ ∣∣ Y ′ ∣ e ( X , Y ) = max { ∣ X ∣ , h } max { ∣ Y ∣ , h } h 2 e ( X , Y ) .
By the density assumption, e ( X , Y ) ≥ ρ ( k − 1 ) ∣ X ∣ ∣ Y ∣ e(X,Y) \ge\rho(k - 1)\sqrt{|X||Y|} e ( X , Y ) ≥ ρ ( k − 1 ) ∣ X ∣∣ Y ∣ and, since d ( X , Y ) ≤ e ( X , Y ) d(X,Y) \le\sqrt{e(X,Y)} d ( X , Y ) ≤ e ( X , Y ) , also e ( X , Y ) ≥ ρ 2 ( k − 1 ) 2 e(X,Y) \ge\rho^2(k - 1)^2 e ( X , Y ) ≥ ρ 2 ( k − 1 ) 2 . If one side has at most h h h vertices, one factor in the denominator of the averaging bound is h h h and the other is at most B k Bk B k . We therefore keep at least an h / ( B k ) h/(Bk) h / ( B k ) fraction of the edges, so e ( X ′ , Y ′ ) ≥ h ρ 2 ( k − 1 ) 2 / ( B k ) e(X',Y') \ge h\rho^2(k-1)^2/(Bk) e ( X ′ , Y ′ ) ≥ h ρ 2 ( k − 1 ) 2 / ( B k ) . Otherwise, ∣ X ∣ , ∣ Y ∣ > h |X|,|Y| > h ∣ X ∣ , ∣ Y ∣ > h , so the denominator in the averaging bound is ∣ X ∣ ∣ Y ∣ |X||Y| ∣ X ∣∣ Y ∣ . Since ∣ X ∣ ∣ Y ∣ ≤ B k \sqrt{|X||Y|} \le Bk ∣ X ∣∣ Y ∣ ≤ B k ,
e ( X ′ , Y ′ ) ≥ h 2 ρ ( k − 1 ) ∣ X ∣ ∣ Y ∣ ≥ h 2 ρ ( k − 1 ) B k ≥ h ρ 2 ( k − 1 ) 2 2 B k , e(X',Y') \ge\frac{h^2\rho(k-1)}{\sqrt{|X||Y|}} \ge\frac{h^2\rho(k-1)}{Bk} \ge\frac{h\rho^2(k-1)^2}{2Bk}, e ( X ′ , Y ′ ) ≥ ∣ X ∣∣ Y ∣ h 2 ρ ( k − 1 ) ≥ B k h 2 ρ ( k − 1 ) ≥ 2 B k h ρ 2 ( k − 1 ) 2 ,
using h ≥ ( k − 1 ) / 2 h \ge(k-1)/2 h ≥ ( k − 1 ) /2 and ρ ≤ 1 \rho\le1 ρ ≤ 1 . In either case,
e J ( U ) ≥ h ρ 2 ( k − 1 ) 2 4 B k ≥ ρ 2 16 B ( k 2 ) , e_J(U) \ge\frac{h\rho^2(k-1)^2}{4Bk} \ge\frac{\rho^2}{16B}\binom{k}{2}, e J ( U ) ≥ 4 B k h ρ 2 ( k − 1 ) 2 ≥ 16 B ρ 2 ( 2 k ) ,
using h ≥ ( k − 1 ) / 2 h \ge(k-1)/2 h ≥ ( k − 1 ) /2 and k − 1 ≥ k / 2 k-1 \ge k/2 k − 1 ≥ k /2 .
Lemma D.5. For a simple graph J J J on N ≥ k ≥ 2 N \ge k \ge2 N ≥ k ≥ 2 vertices and its bipartite double cover G G G , 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 , B ≥ 1 B \ge1 B ≥ 1 , and an algorithm A that returns ⊥ \bot ⊥ or nonempty sets X ⊆ L X \subseteq L X ⊆ L and Y ⊆ R Y \subseteq R Y ⊆ R with ∣ X ∣ , ∣ Y ∣ ≤ B k |X|,|Y| \le Bk ∣ X ∣ , ∣ Y ∣ ≤ B k from every v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , we can find, with 2 N 2N 2 N calls to A and polynomial additional time, a set U U U of k k k vertices of J J J such that, if A( G , v , k ) (G,v,k) ( G , v , k ) returns sets X , Y X,Y X , Y with d ( X , Y ) ≥ ρ ( k − 1 ) d(X,Y) \ge\rho(k-1) d ( X , Y ) ≥ ρ ( k − 1 ) for some v v v , then
e J ( U ) ≥ ρ 2 16 B ( k 2 ) . e_J(U) \ge\frac{\rho^2}{16B}\binom{k}{2}. e J ( U ) ≥ 16 B ρ 2 ( 2 k ) .
Proof. We run A from every vertex of G G G , apply the construction in Lemma D.4 to each output X , Y X,Y X , Y , and keep a set inducing the most edges. If every call returns ⊥ \bot ⊥ , we take any k k k vertices. If A returns sets X , Y X,Y X , Y with d ( X , Y ) ≥ ρ ( k − 1 ) d(X,Y) \ge\rho(k-1) d ( X , Y ) ≥ ρ ( k − 1 ) , then by Lemma D.4 the corresponding set of k k k vertices satisfies the claimed bound, as does the set we keep. We construct the double cover and select the sets of k k k vertices in polynomial time.
The limitation under SPCH
Definition D.6 (Strongish Planted Clique Hypothesis [30 Hypothesis 1] ). The Strongish Planted Clique Hypothesis (SPCH) is the assumption that, for some 0 < θ < 1 / 2 0 < \theta< 1/2 0 < θ < 1/2 , no randomized algorithm running in time n o ( log 2 n ) n^{o(\log_2 n)} n o ( l o g 2 n ) distinguishes the random graph G ( n , 1 2 ) G(n,\frac{1}{2}) G ( n , 2 1 ) on n n n vertices, in which each edge is present independently with probability 1 / 2 1/2 1/2 , from the same graph G ( n , 1 2 , ⌈ n θ ⌉ ) G(n,\frac{1}{2},\lceil n^\theta\rceil) G ( n , 2 1 , ⌈ n θ ⌉) with a clique added on ⌈ n θ ⌉ \lceil n^\theta\rceil ⌈ n θ ⌉ uniformly chosen vertices, with success probability at least 2 / 3 2/3 2/3 under each distribution. We call these the no and yes distributions, respectively. The probability is over the input graph and the algorithm’s randomness.
We use the following hardness theorem for Densest k k k -Subgraph, with the promise that the input contains a k k k -clique.
Theorem D.7 ([30 Theorem 2] ). Assuming SPCH, for every β \beta β with β ( k ) = o ( k ) \beta(k)=o(k) β ( k ) = o ( k ) and every computable f f f , no algorithm, given an N N N -vertex graph J J J and k k k such that J J J contains a k k k -clique, returns in time f ( k ) N O ( 1 ) f(k)N^{O(1)} f ( k ) N O ( 1 ) a set U U U of k k k vertices with
e J ( U ) ≥ 1 β ( k ) ( k 2 ) . e_J(U) \ge\frac{1}{\beta(k)}\binom{k}{2}. e J ( U ) ≥ β ( k ) 1 ( 2 k ) .
Theorem D.8 (Limitations on the output size under SPCH). Assuming SPCH, for a constant 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 and ϕ ( k ) = o ( k 2 ) \phi(k)=o(k^2) ϕ ( k ) = o ( k 2 ) , if a possibly randomized algorithm A as in Definition D.1 has output bound ϕ \phi ϕ and runs in time f ( k ) ∣ V ∣ O ( 1 ) f(k)|V|^{O(1)} f ( k ) ∣ V ∣ O ( 1 ) on every input ( G , v , k ) (G,v,k) ( G , v , k ) , for a computable function f f f of k k k alone, then, for some k ≥ 2 k \ge2 k ≥ 2 , there is a simple bipartite graph G G G with cohesive sets S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R of k k k vertices each, such that from every v ∈ S ∪ ˙ T v \in S \mathbin{\dot\cup} T v ∈ S ∪ ˙ T the output is ⊥ \bot ⊥ or has density below ρ d ( S , T ) \rho\,d(S,T) ρ d ( S , T ) with probability greater than 1 / 3 1/3 1/3 .
Proof of Theorem D.8. Suppose, for a contradiction, that for every k ≥ 2 k \ge2 k ≥ 2 and all cohesive target sets S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R of k k k vertices each, the algorithm A returns sets X , Y X,Y X , Y with d ( X , Y ) ≥ ρ d ( S , T ) d(X,Y) \ge\rho d(S,T) d ( X , Y ) ≥ ρ d ( S , T ) from some v ∈ S ∪ ˙ T v \in S \mathbin{\dot\cup} T v ∈ S ∪ ˙ T with probability at least 2 / 3 2/3 2/3 . For J J J with a k k k -clique, the two copies S , T S,T S , T of the clique in the double cover are cohesive with d ( S , T ) = k − 1 d(S,T)=k-1 d ( S , T ) = k − 1 . We run A from every vertex of G G G and form a set of k k k vertices of J J J from each returned pair X , Y X,Y X , Y as in the proof of Lemma D.4. Among these sets, we keep one with the most edges between its vertices. By Lemma D.5 with B = 1 + ϕ ( k ) / k B=1+\phi(k)/k B = 1 + ϕ ( k ) / k , we can find a set U U U of k k k vertices inducing at least ( k 2 ) / β ( k ) \binom{k}{2}/\beta(k) ( 2 k ) / β ( k ) edges with probability at least 2 / 3 2/3 2/3 , where
β ( k ) : = 16 ( k + ϕ ( k ) ) ρ 2 k = o ( k ) . \beta(k) := \frac{16(k+\phi(k))}{\rho^{2}k}=o(k). β ( k ) := ρ 2 k 16 ( k + ϕ ( k )) = o ( k ) .
We can compute e J ( U ) e_J(U) e J ( U ) for each returned set, so we repeat the procedure in Lemma D.5 independently a constant number of times (concretely, five) and keep a set inducing the most edges. The subgraph induced by this set contains at least ( k 2 ) / β ( k ) \binom{k}{2}/\beta(k) ( 2 k ) / β ( k ) edges with probability at least 1 − 3 − 5 > 0.99 1-3^{-5}>0.99 1 − 3 − 5 > 0.99 . The running time is f ′ ( k ) N O ( 1 ) f'(k)N^{O(1)} f ′ ( k ) N O ( 1 ) for a computable f ′ f' f ′ .
In the reduction from planted clique in Manurangsi et al. [30 ] , completeness and soundness each hold with probability at least 0.9 0.9 0.9 . We use the procedure in Lemma D.5, with the five independent repetitions, as the Densest k k k -Subgraph algorithm in that reduction. We then distinguish the YES and NO distributions of SPCH (Definition D.6) with success probability at least 0.9 ⋅ 0.99 > 2 / 3 0.9\cdot0.99>2/3 0.9 ⋅ 0.99 > 2/3 under each distribution, contradicting SPCH. □ \square □
Remark. We do not require β \beta β in Theorem D.7 to be nondecreasing. In Manurangsi et al. [30 ] , the ratio is a function g ( k ) ≤ k g(k)\le k g ( k ) ≤ k growing with k k k , so we replace β \beta β with the nondecreasing β ~ ( k ) : = max 1 ≤ j ≤ k β ( j ) \widetilde{\beta}(k):=\max_{1\le j\le k}\beta(j) β ( k ) := max 1 ≤ j ≤ k β ( j ) . For every δ > 0 \delta>0 δ > 0 , with C δ ≥ 0 C_\delta\ge0 C δ ≥ 0 bounding β ( j ) \beta(j) β ( j ) for the finitely many j j j with β ( j ) > δ j \beta(j)>\delta j β ( j ) > δ j , β ~ ( k ) ≤ max { C δ , δ k } \widetilde{\beta}(k)\le\max\{C_\delta,\delta k\} β ( k ) ≤ max { C δ , δ k } , so β ~ = o ( k ) \widetilde{\beta}=o(k) β = o ( k ) . In particular, β ~ ( k ) ≤ k \widetilde{\beta}(k)\le k β ( k ) ≤ k for all sufficiently large k k k , and exhaustive search handles the remaining values of k k k .
Corollary D.9 (Approximation and output size under SPCH). Assuming SPCH, for α ( k ) ≥ 1 \alpha(k)\ge1 α ( k ) ≥ 1 with α ( k ) = o ( k ) \alpha(k)=o(\sqrt{k}) α ( k ) = o ( k ) and ϕ ( k ) = o ( k 2 / α ( k ) 2 ) \phi(k)=o(k^{2}/\alpha(k)^{2}) ϕ ( k ) = o ( k 2 / α ( k ) 2 ) , no algorithm as in Definition D.1 with output bound ϕ \phi ϕ and running time f ( k ) ∣ V ∣ O ( 1 ) f(k)|V|^{O(1)} f ( k ) ∣ V ∣ O ( 1 ) for a computable f f f guarantees, for every k ≥ 2 k\ge2 k ≥ 2 and every cohesive target S , T S,T S , T of k k k vertices per side, an output of density at least d ( S , T ) / α ( k ) d(S,T)/\alpha(k) d ( S , T ) / α ( k ) from some starting vertex in S ∪ ˙ T S\mathbin{\dot\cup}T S ∪ ˙ T .
Proof. For such an algorithm, by Lemma D.5 with ρ = 1 / α ( k ) \rho=1/\alpha(k) ρ = 1/ α ( k ) and B = 1 + ϕ ( k ) / k B=1+\phi(k)/k B = 1 + ϕ ( k ) / k , we obtain an approximation ratio β ( k ) : = 16 α ( k ) 2 ( k + ϕ ( k ) ) / k \beta(k):=16\alpha(k)^{2}(k+\phi(k))/k β ( k ) := 16 α ( k ) 2 ( k + ϕ ( k )) / k for Densest k k k -Subgraph, with
β ( k ) k = 16 ( α ( k ) 2 k + α ( k ) 2 ϕ ( k ) k 2 ) ⟶ 0. \frac{\beta(k)}{k}=16\left(\frac{\alpha(k)^{2}}{k}+\frac{\alpha(k)^{2}\phi(k)}{k^{2}}\right)\longrightarrow0. k β ( k ) = 16 ( k α ( k ) 2 + k 2 α ( k ) 2 ϕ ( k ) ) ⟶ 0.
The running time is f ′ ( k ) N O ( 1 ) f'(k)N^{O(1)} f ′ ( k ) N O ( 1 ) for a computable f ′ f' f ′ , contradicting Theorem D.7. Following the proof of Theorem D.8 with ρ = 1 / α ( k ) \rho=1/\alpha(k) ρ = 1/ α ( k ) , we also rule out algorithms that use randomness, always respect the bounds on output size and running time, and succeed with probability at least 2 / 3 2/3 2/3 . □ \square □
Quadratic output on the reduction instances. When J J J contains a k k k -clique, we can achieve a quadratic output bound on its bipartite double cover in time k O ( k ) N O ( 1 ) k^{O(k)}N^{O(1)} k O ( k ) N O ( 1 ) . If a vertex of J J J has at least k 2 k^{2} k 2 neighbors, one of its copies and k 2 k^{2} k 2 of that copy’s neighbors form a star of density k k k . Otherwise, every neighborhood in J J J has fewer than k 2 k^{2} k 2 vertices, and we find the promised k k k -clique by testing all ( k − 1 ) (k-1) ( k − 1 ) -subsets of each neighborhood together with its center. The two copies of the clique have density k − 1 k-1 k − 1 . Thus, on these instances, subquadratic output is essential to the lower bound even with full graph access.
The limitation under ETH
Definition D.10 (Exponential Time Hypothesis [19 ] ). The Exponential Time Hypothesis (E T H ETH E T H ) is the assumption that 3-SAT for formulas with m m m clauses cannot be decided in time 2 o ( m ) 2^{o(m)} 2 o ( m ) . By the sparsification lemma of Impagliazzo et al. (2001), this is equivalent to the formulation in terms of variables.
We use the following hardness theorem, in which the graph contains a k k k -clique in the YES case.
Theorem D.11 ([29 Theorem 1] ). Assuming E T H ETH E T H , there is a constant c 0 > 0 c_0 > 0 c 0 > 0 such that no polynomial-time algorithm, given a graph J J J on N ≥ 4 N \ge4 N ≥ 4 vertices and an integer 2 ≤ k ≤ N 2 \le k \le N 2 ≤ k ≤ N , distinguishes the case that J J J contains a k k k -clique from the case that every k k k -vertex subgraph of J J J contains at most ( k 2 ) / χ ( N ) \binom{k}{2}/\chi(N) ( 2 k ) / χ ( N ) edges, where
χ ( N ) : = N 1 / ( log 2 log 2 N ) c 0 . \chi(N) := N^{1/(\log_2 \log_2 N)^{c_0}}. χ ( N ) := N 1/ ( l o g 2 l o g 2 N ) c 0 .
Theorem D.12 (Limitations on the output size under E T H ETH E T H ). Assuming E T H ETH E T H , for constants 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 and c ≥ 1 c \ge1 c ≥ 1 , if a deterministic polynomial-time algorithm A A A returns ⊥ \bot ⊥ or nonempty sets X ⊆ L X \subseteq L X ⊆ L and Y ⊆ R Y \subseteq R Y ⊆ R with ∣ X ∣ , ∣ Y ∣ ≤ c k log 2 c ( 2 + k + Δ ) |X|, |Y| \le c k \log_2^c(2 + k + \Delta) ∣ X ∣ , ∣ Y ∣ ≤ c k log 2 c ( 2 + k + Δ ) on every input ( G , v , k ) (G,v,k) ( G , v , k ) , then, for some k ≥ 2 k \ge2 k ≥ 2 , there is a simple bipartite graph G G G with cohesive sets S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R of k k k vertices each, such that from every v ∈ S ∪ ˙ T v \in S \mathbin{\dot\cup} T v ∈ S ∪ ˙ T the output is ⊥ \bot ⊥ or has density below ρ d ( S , T ) \rho d(S,T) ρ d ( S , T ) . The same conclusion holds for running time polynomial in k k k , Δ \Delta Δ and log 2 ∣ V ∣ \log_2 |V| log 2 ∣ V ∣ .
Proof. Suppose, for a contradiction, that for all cohesive target sets S ⊆ L S \subseteq L S ⊆ L and T ⊆ R T \subseteq R T ⊆ R , the algorithm A A A returns sets X , Y X,Y X , Y with d ( X , Y ) ≥ ρ d ( S , T ) d(X,Y) \ge\rho d(S,T) d ( X , Y ) ≥ ρ d ( S , T ) from some v ∈ S ∪ ˙ T v \in S \mathbin{\dot\cup} T v ∈ S ∪ ˙ T . For an N N N -vertex graph J J J and k ≤ N k \le N k ≤ N , the double cover has Δ < N \Delta< N Δ < N , so the output bound is at most B k Bk B k for B : = c ⌈ log 2 ( 4 N ) ⌉ c B := c\lceil\log_2(4N)\rceil^c B := c ⌈ log 2 ( 4 N ) ⌉ c , and we apply the procedure of Lemma D.5. If J J J contains a k k k -clique, its two copies S , T S,T S , T are cohesive with d ( S , T ) = k − 1 d(S,T) = k - 1 d ( S , T ) = k − 1 , so A A A returns sets X , Y X,Y X , Y with d ( X , Y ) ≥ ρ ( k − 1 ) d(X,Y) \ge\rho(k - 1) d ( X , Y ) ≥ ρ ( k − 1 ) from some vertex, and the set U U U of Lemma D.5 satisfies
e J ( U ) ≥ ρ 2 16 B ( k 2 ) > 1 χ ( N ) ( k 2 ) e_J(U) \ge\frac{\rho^2}{16B}\binom{k}{2} > \frac{1}{\chi(N)}\binom{k}{2} e J ( U ) ≥ 16 B ρ 2 ( 2 k ) > χ ( N ) 1 ( 2 k )
for all sufficiently large N N N , since χ ( N ) \chi(N) χ ( N ) grows faster than every power of log 2 N \log_2 N log 2 N . In the other case of the promise, every set of k k k vertices, including U U U , induces at most ( k 2 ) / χ ( N ) \binom{k}{2}/\chi(N) ( 2 k ) / χ ( N ) edges. By comparing e J ( U ) e_J(U) e J ( U ) with ( k 2 ) / χ ( N ) \binom{k}{2}/\chi(N) ( 2 k ) / χ ( N ) , we can therefore distinguish the two cases of Theorem D.11 in polynomial time, with exhaustive search for bounded N N N . Finally, a running time polynomial in k k k , Δ \Delta Δ and log 2 ∣ V ∣ \log_2 |V| log 2 ∣ V ∣ is polynomial in ∣ V ∣ |V| ∣ V ∣ when k ≤ ∣ V ∣ k \le|V| k ≤ ∣ V ∣ and Δ < ∣ V ∣ \Delta< |V| Δ < ∣ V ∣ . □
Why the limitation under ETH is weaker. We cannot obtain the quadratic bound of Theorem D.8 from the hard instances used under E T H ETH E T H , because they have N = k 1 + o ( 1 ) N = k^{1+o(1)} N = k 1 + o ( 1 ) vertices. Manurangsi [29 ] constructs graphs whose vertices are partial assignments to ℓ \ell ℓ of the n n n variables of a 3-SAT formula. Each graph has N = 2 ℓ ( n ℓ ) N = 2^{\ell}\binom{n}{\ell} N = 2 ℓ ( ℓ n ) vertices. If the formula is satisfiable, the restrictions of a satisfying assignment to all ℓ \ell ℓ -element sets of variables form a clique of size k = ( n ℓ ) k = \binom{n}{\ell} k = ( ℓ n ) . With the parameter choices in that proof, ℓ = o ( n ) \ell= o(n) ℓ = o ( n ) . Hence
log 2 N log 2 k = 1 + ℓ log 2 k ≤ 1 + 1 log 2 ( n / ℓ ) = 1 + o ( 1 ) . \frac{\log_2 N}{\log_2 k} = 1 + \frac{\ell}{\log_2 k} \le1 + \frac{1}{\log_2(n/\ell)} = 1 + o(1). log 2 k log 2 N = 1 + log 2 k ℓ ≤ 1 + log 2 ( n / ℓ ) 1 = 1 + o ( 1 ) .
For fixed 0 < δ < 1 0 < \delta< 1 0 < δ < 1 and large k k k , the entire double cover has fewer than k 2 − δ k^{2-\delta} k 2 − δ vertices per side, and nonempty subsets X ⊆ L X \subseteq L X ⊆ L and Y ⊆ R Y \subseteq R Y ⊆ R maximizing d ( X , Y ) d(X,Y) d ( X , Y ) can then be found in polynomial time (Charikar [9 ] ), meeting the output bound k 2 − δ k^{2-\delta} k 2 − δ with approximation ratio one.