Detecting High Log-Densities – an O(n1/4) Approximation for Densest k-Subgraph Aditya Bhaskara ∗ Moses Charikar † Eden Chlamtac ‡ Uriel Feige § Aravindan Vijayaraghavan ¶ 0 1 0 2 Abstract n a In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find J a subgraph of G induced on k vertices that contains the largest number of edges. There is a 7 significantgapbetweenthebestknownupperandlowerboundsforthisproblem. ItisNP-hard, 1 and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, ] thecurrentbestknownalgorithmofFeige,KortsarzandPeleg[FKP01],givesanapproximation S ratio of n1/3−ε for some specific ε>0 (estimated by those authors at around ε=1/60). D Wepresentanalgorithmthatforeveryε>0approximatestheDensestk-Subgraphproblem s. within a ratio of n1/4+ε in time nO(1/ε). If allowed to run for time nO(logn), our algorithm c achieves an approximation ratio of O(n1/4). Our algorithm is inspired by studying an average- [ caseversionofthe problemwherethe goalistodistinguishrandomgraphsfromrandomgraphs 1 withplanteddensesubgraphs–theapproximationratioweachieveforthegeneralcasematches v the “distinguishing ratio” we obtain for this planted problem. Achieving a distinguishing ratio 1 of o(n1/4) for the planted problem (in polynomial time) is beyond the reach of our current 9 8 techniques. 2 At a high level, our algorithms involve cleverly counting appropriately defined trees of con- . stant size in G, and using these counts to identify the vertices of the dense subgraph. Our 1 0 algorithm is based on the following principle. We say that a graph G(V,E) has log-density α if 0 its average degree is Θ(V α). The algorithmic core of our result is a family of algorithms that 1 output k-subgraphs of n|on|trivial density whenever the log-density of the densest k-subgraph is : v larger than the log-density of the host graph. i Finally, we extend this algorithm to obtain an O(n1/4−ε)-approximation algorithm which X runs in time O(2nO(ε)) and also explore various approaches to obtain better approximation r a algorithms in restricted parameter settings for random instances. ∗Department of Computer Science, Princeton University, supported by NSF awards mspa-mcs 0528414, CCF 0832797, and AF0916218. Email: [email protected] †Department of Computer Science, Princeton University, supported by NSF awards mspa-mcs 0528414, CCF 0832797, and AF0916218. Email: [email protected] ‡WeizmannInstituteofScience,Rehovot,Israel,supportedbyaSirCharlesClorePostdoctoralFellowship. Email: [email protected] §WeizmannInstituteofScience,Rehovot,Israel. Email: [email protected]. TheauthorholdstheLawrence G.HorowitzProfessorialChairattheWeizmannInstitute. WorksupportedinpartbyTheIsraelScienceFoundation (grant No. 873/08). ¶Department of Computer Science, Princeton University, supported by NSF awards mspa-mcs 0528414, CCF 0832797, and AF0916218. Email: [email protected] 1 1 Introduction In this paper, we study the Densest k-Subgraph (DkS) problem: Given a graph G and parameter k, find a subgraph of G on k vertices with maximum density (average degree). This problem may be seen as an optimization version of the classical NP-complete decision problem CLIQUE. The approximability of DkS is an important open problem and despite much work, there remains a significant gap between the currently best known upper and lower bounds. InadditiontobeingNP-hard(as seenbytheconnection toCLIQUE),theDkSproblemhasalso been shown not to admit a PTAS under various complexity theoretic assumptions. Feige [Fei02] has shown this assuming random 3-SAT formulas are hard to refute, while more recently this was shown by Khot [Kho04] assuming that NP does not have randomized algorithms that run in sub-exponential time (i.e. that NP BPTIME(2nε)). ε>0 6⊆ ∩ The current best approximation ratio of n1/3−ε for some small ε > 0 (which has been esti- mated to be roughly 1/60) was achieved by Feige, Kortsarz and Peleg [FKP01]. Other known approximation algorithms have approximation guarantees that depend on the parameter k. The greedy heuristic of Asahiro et al. [AHI02] obtains an O(n/k) approximation. Linear and semidefi- nite programming (SDP) relaxations were studied by Srivastav and Wolf [SW98] and by Feige and Langberg [FL01], where the latter authors show how they can be used to get approximation ratios somewhat better than n/k. Feige and Seltser [FS97] show graphs for which the integrality gap of the natural SDP relaxation is Ω(n1/3), indicating that in the worst case, the approximation ratios achieved in [FKP01] are better than those achievable by this SDP. When the input is a complete graph with edge weights that satisfy the triangle inequality, a simple greedy algorithm achieves an approximation ratio of 2 (though the analysis of this algorithm is apparently not easy, see [BG09]). A related problem to DkS is the max density subgraph problem, where the aim is to find a subgraph H which maximizes the ratio of number of edges to number of vertices in H. It turns out that this can be solved in polynomial time [GGT89]. Charikar et al. [CHK09] recently showed an O(n1/3) approximation to the maximization version of label cover. This problem is at least as difficult as DkS in the sense that there is an approximation preserving randomized reduction from DkS (see [CHK09] for example) to it. No reduction in the opposite direction is known. Our algorithm for DkS is inspired by studying an average-case version we call the ‘Dense vs Random’ question (see Section 3 for a precise definition). Here the aim is to distinguish random graphs from graphs containing a dense subgraphs, which can be viewed as the task of efficiently certifying that random graphs do not contain dense subgraphs. This distinguishing problem is similar in flavour to the well-studied planted clique problem (see [AKS98]). Getting a better understanding of this planted question seems crucial for further progress on DkS. Some recent papers have used the hypothesis that (bipartite versions of) the planted dense subgraph problem is computationally hard: Applebaum et al. [ABW08] use this in the design of a new public key encryption scheme. More recently, Arora et al. [ABBG10] use this to demonstrate that evaluating certain financial derivatives is computationally hard. The use of such hardness assumptions provides additional motivation for the study of algorithms for these problems. 1.1 Our results Ourmain resultis a polynomial time O(n1/4+ε) approximation algorithm for DkS,for any constant ε > 0. That is, given ε > 0, and a graph G with a k-subgraph of density d, our algorithm outputs a k-subgraph of density Ω d/n1/4+ε in polynomial time. In particular, our techniques give an (cid:0) (cid:1) 1 O(n1/4)-approximation algorithm running in O(nlogn) time. At a high level, our algorithms involve cleverly counting appropriately defined subgraphs of constant size in G, and use these counts to identify the vertices of the dense subgraph. A key notion which comes up in the analysis is the following: Definition 1.1. The log-density of a graph G(V,E) with average degree D is log D. In other |V| words, if a graph has log-density α, its average degree is V α. 1 | | We first consider the random setting – distinguishing between G drawn from G(n,p), and G containing a k-subgraph H of certain density planted in it. In fact, we examine a few variants (i.e. in the second case each of G and H may or may not be random). For all these variants we show that if the log-density of G is α and that of H is β, with β > α, we can solve the distinguishing problem in time nO(1/(β−α)). Our main technical contribution is that a result of this nature can be proven for arbitrary graphs. Informally, our main result, which gives a family of algorithms, parametrized by a rational number r/s, can be stated as follows (see Theorem 4.5 for a more precise statement): Theorem 1.2. (informal) Let s > r > 0 be relatively prime integers, let G be an undirected graph with maximum degree D = nr/s, which contains a k-subgraph H with average degree d. Then there is an algorithm running in time nO(r) that finds a k-subgraph of average degree Ω(d/D(s−r)/s). Note that the log-density of H does not explicitly occur in the statement of the theorem. However, it turns out we can pre-process the graph, and restrict ourselves to the case kD = n (see AppendixA.2), in which case D(s−r)/s = kr/s, thus the output subgraphhas average degree d/kr/s. So if the log-density of H is β (recall that G has log-density r/s), the output graph has density ≤ d/kr/s = kβ−r/s. Thus the difference in the log-densities also plays a role in the case of arbitrary graphs. Alsonotethatthetheoremdeals withthemaximum degreeinG, andnotaverage degree(which defines the log-density). It turns out that this upper-boundon the log-density will suffice (and will be more useful in the analysis). As we observed earlier, we give a family of algorithms parameterized by a rational number. Thus, given G and k, we pick r/s appropriately and appeal to the theorem. In some sense, this familyofalgorithms isasystematic generalization ofthe(somewhatadhoc)algorithmsof[FKP01]. Finally, observe that theorem implies an approximation ratio of at most D(s−r)/s nr(s−r)/s2 ≤ ≤ n1/4 for every choice of s > r > 0. As we mentioned, the statement above is informal. If we choose to restrict the running time to O(ns0) by limiting ourselves to r < s s (i.e. the bound on D will 0 ≤ not be exact), we lose a factor n1/s0 in the approximation. We refer to Section 4 for the details. Outline of techniques. ThedistinguishingalgorithmfortheDensevsRandomproblemisbased on the fact that in G(n,p), instances of any fixed constant size structure appear more often when the graph has a higher log-density. More precisely, given parameters r,s, we will define a (constant size) tree T such that a fixed set of leaves can be completed to many instances of T in a graph r,s r,s with log-density > r/s, whereas in a random graph with log-density < r/s there will only be a negligible number of such instances. Thus, if the log-density of H is greater than r/s, finding a smallsetofvertices inH (andusingthemasleaves ofT )canhelpreveallargerportionsofadense r,s 1We will ignore low order terms when expressing the log-density. For example, graphs with constant average degree will be said to havelog-density 0, and cliques will be said to havelog-density 1. 2 subgraph. Though our intuition comes from random graphs, the heart of the argument carries over to worst-case instances. We use a linear programming relaxation to guide us in our search for the fixed vertices’ assign- ment and obtain the dense subgraph. In order to extract consistent feasible solutions from the LP even under the assumptions that fixed vertices belong to H, the LP relaxation will have a recursive structuresimilar to the Lov´asz-Schrijver hierarchy [LS91]. Feasible solutions to this LP (when they exist) can be found in time nO(r) (where the depth of the recursion will be roughly r), while the rest of the algorithm (given the LP solution) will take linear time. As we shall see, there is also a combinatorial variant of our algorithm, which, rather than relying on an LP solution, finds the appropriate set of leaves by exhaustive search (in time nr+O(1)). While the analysis is essentially the same as for the LP variant, it is our hope that a mathematical programming approach will lead to further improvements in running time and approximation guarantee. The approximation ratio we achieve for general instances of DkS matches the “distinguishing ratio” we are currently able to achieve for various random settings. This suggests the following concrete open problem which seems to be a barrier for obtaining an approximation ratio of n1/4−ε for DkS – distinguish between the following two distributions: : graph G picked from G(n,n−1/2), and 1 D : graphGpickedfromG(n,n−1/2)withtheinducedsubgraphon√nverticesreplaced 2 D with G(√n,n−(1/4+ε)). In section 5 we will see that this distinguishing problem can be solved in time 2nO(ε), and this can be used to give an algorithm for DkS with approximation ratio n1/4−ε, and run time 2nO(ε). These mildly exponential algorithms are interesting given the recent results of [ABBG10] and [ABW08], which are based on the assumption that planted versions of DkS are hard. In section 6, we show that in the random setting we can beat the log-density based algorithms for certain ranges of parameters. We use different techniques for different random models, some of which are very different from those used in sections 3 and 4. Interestingly, none of these techniques give a distinguishing ratio better than n1/4 when k = D = √n. 1.2 Organization of paper In Section 2, we introduce some notation, and describesimplifyingassumptions which will bemade in later sections (some of these were used in [FKP01]). In Section 3, we consider two natural ‘planted’ versions of DkS, and present algorithms for these versions. The analysis there motivates our approximation algorithm for DkS, which will be presented in Section 4. In Section 5 and Section 6, we explore approaches to overcome the log-density barrier that limits our algorithms in Section 4. In Section 5 we give an O(n1/4−ε) approximation algorithm for arbitrary graphs with run time O(2nO(ε)) time, and in Section 6, we show that in various random settings, we can obtain a √D-approximation (which is better than the log-density guarantee for 1 < D < √n). 2 Notation and some simplifications We now introduce some notation which will be used in the rest of the paper. Unless otherwise stated, G(V,E) refers to an input graph on n vertices, and k refers to the size of the subgraph we are required to output. Also, H will denote the densest k-subgraph (breaking ties arbitrarily) in 3 G, and d denotes the average degree of H. For v V, Γ(v) denotes the set of neighbors of v, and ∈ for a set of vertices S V, Γ(S) denotes the set of all neighbors of vertices in S. Finally, for any ⊆ number x R, will use the notation fr(x) = x x . ∈ −⌊ ⌋ We will make the following simplifying assumptions in the remaining sections: (these are justi- fied in Section A of the appendix) 1. There exists a D such that (a) the maximum degree of G is at most D, and (b) a greedy algorithm finds a k-subgraph of density max 1,kD/n in G. { } 2. d is the minimum degree in H (rather than the average degree) 3. It suffices to find a subgraph of size at most k, rather than exactly k. In Section 4 we use ‘k-subgraph’ more loosely to mean a subgraph on at most k vertices. 4. When convenient, we may also take G (and hence H) to be bipartite. 5. The edges of the graph G are assumed to be unweighted, since we can bucket the edges into O(logn) levels according to the edge weights (which we assume are all positive), and output the densest of the k-subgraphs obtained by applying the algorithm to each of the graphs induced by the edges in a bucket. This incurs a loss of just O(logn) factor in the approximation. In many places, we will ignore leading constant factors (for example, we may find a subgraph of size 2k instead of k). It will be clear that these do not seriously affect the approximation factor. 3 Random graph models An f(n)-approximation algorithm for the densest k-subgraph problem must be able to distinguish between graphs where any k-subgraph has density at most c, and graphs with an cf(n)-dense k-subgraph planted in them. Random graphs are a natural class of graphs that do not contain dense k-subgraphs. Further, random graphs seem to present challenges for currently best known algorithms for DkS. Hence, it is instructive to see what parameters allow us to efficiently solve this distinguishing problem. Weconsiderthreevariantsoftherandomdistinguishingproblem,inincreasingorderofdifficulty. In the Random Planted Model, we would like to distinguish between two distributions: : Graph G is picked from G(n,p), with p = nα−1, 0 < α< 1. 1 D : G is picked from G(n,nα−1) as before. A set S of k vertices is chosen arbitrarily, 2 D and the subgraph on S is replaced with a random graph H from G(k,kβ−1) on S. Aslightly hardervariantistheDense in Random problem,inwhichwewouldliketodistinguish betweenGchosenfrom ,asbefore,andGwhichischosensimilarlyto ,exceptthattheplanted 1 2 D D subgraph H is now an arbitrary graph with average degree kβ (that is, log-density β). Here, the algorithm must be able to detect the second case with high probability regardless of the choice of H. Finally, we consider the Dense versus Random problem, in which we would like to distinguish between G , and an arbitrary graph G which contains a k-subgraph H of log-density β. 1 ∼ D 4 Observe that for G , a k-subgraph would have expected average degree kp = knα−1. 1 ∼ D Further, it can be shown that densest k-subgraph in G will have average degree max knα−1,1 , { } w.h.p. (up to a logarithmic factor). Thus if we can solve the distinguishing problem above, its ‘distinguishing ratio’ would be min (kβ/max knα−1,1 ), where β ranges over all values for which β { } we can distinguish (for the corresponding values of k,α). If this is the case for all β > α, then (as follows from a straightforward calculation), the distinguishing ratio is never more than kα n 1−α = min ,kα max knα−1,1 k { } (cid:26)(cid:16) (cid:17) (cid:27) n1−α 1−α k α = nα(1−α) min , · k n1−α ( ) (cid:18) (cid:19) (cid:18) (cid:19) nα(1−α) ≤ n1/4. ≤ In this section we will only discuss the Random Planted Model and the Dense versus Random problem, while the intermediate Dense in Random problem is only examined in Section 6. 3.1 The random planted model OneeasywayofdistinguishingbetweenthetwodistributionsintheRandomPlantedModelinvolves looking at the highest degree vertices, or at the pairs of vertices with the largest intersection of neighborhoods. This approach, which is discussed in Section 6 is not only a distinguishing algorithm, but can also identify H in the case of G . However, it is not robust, in the sense 2 ∼ D that we can easily avoid a detectable contribution to the degrees of vertices of H by resampling the edges between H and G H with the appropriate probability. \ Rather, we examine a different approach, which is to look for constant size subgraphs H′ which act as ‘witnesses’. If G , we want that w.h.p. G will not have a subgraph isomorphic to H′, 1 ∼ D while if G , w.h.p. G should have such a subgraph. It turns out that whenever β > α, such 2 ∼ D an H′ can be exists, and thus we can solve the distinguishing problem. Standard probabilistic analysis (cf. [AS08]) shows that if a graph has log-density greater than r/s (for fixed integers 0 < r < s) then it is expected to have constant size subgraphs in which the ratio of edges to vertices is s/(s r), and if the log-density is smaller than r/s, such subgraphs are − not likely to exist (i.e., the occurrence of such subgraphs has a threshold behavior). Hence such subgraphs can serve as witnesses when α< r/s < β. Observe that in the approach outlined above, r/s is rational, and the size of the witnesses increases as r and s increase. This serves as intuition as to why the statement of Theorem 1.2 involves a rational number r/s, with the running time depending on the value of r. 3.2 Dense versus Random The random planted model above, though interesting, does not seem to say much about the gen- eral DkS problem. In particular, for the Dense versus Random problem, simply looking for the occurrence of subgraphs need not work, because the planted graph could be very dense and yet not have the subgraph we are looking for. To overcome this problem, we will use a different kind of witness, which will involve special constant-size trees, which we call templates. In a template witness based on a tree T, we fix a 5 small set of vertices U in G, and count the number of trees isomorphic to T whose set of leaves is exactly U. The templates are chosen such that a random graph with log-density below a threshold will have a count at most poly-logarithmic for every choice of U, while we will show by a counting argument that in any graph (or subgraph) with log-density above the same threshold, there exists a set of vertices U which coincide with the leaves of at least nε copies of T (for some constant ε > 0). As noted in Section 2, we may assume minimum degree kβ in H as opposed to average degree (this will greatly simplify the counting argument). As an example, suppose the log-density is 2/3. In this case, the template T we consider is the tree K (a claw with three leaves). For any triple of vertices U, we count the number of copies 1,3 of T with U as the set of leaves – in this case this is precisely the number of common neighbors of the vertices in U. In this case, we show that if G , with α 2/3, every triple of vertices has 1 ∼ D ≤ at most O(logn) common neighbors. While in the dense case, with β = 2/3+ε, there exists some triple with at least kε common neighbors. Since for ranges of parameters of interest kε = ω(logn), we have a distinguishing algorithm. Letusnowconsideralog-density thresholdofr/s(forsomerelatively primeintegers s > r > 0). Thetree T we will associate with the correspondingtemplate witness will bea caterpillar – a single path called the backbone from which other paths, called hairs, emerge. In our case, the hairs will all be of length 1. More formally, Definition 3.1. An (r,s)-caterpillar is a tree constructed inductively as follows: Begin with a single vertex as the leftmost node in the backbone. For s steps, do the following: at step i, if the interval [(i 1)r/s,ir/s] contains an integer, add a hair of length 1 to the rightmost vertex in the − backbone; otherwise, add an edge to the backbone (increasing its length by 1). This inductive definition is also useful in deriving an upper bound on the number of (r,s)- caterpillars in G(n,p) (for p nr/s−1) with a fixed sequence of ‘leaves’ (end-points of the hairs) ≤ v ,v ,...,v . We do this by bounding the number of candidates for each internal (backbone) 0 1 r vertex, and showing that with high probability, this is at most O(logn). We begin by bounding the number of candidates for the rightmost backbone vertex in a prefix of the (r,s) caterpillar (as per the above inductive construction). For each t = 1,...,r, let us write S (t) for the set v0,...,v⌊tr/s⌋ of such candidates at step t (given the appropriate prefix of leaves). The following claim upper bounds the cardinality of these sets (with high probability). (Recall the notation fr(x) =x x .) −⌊ ⌋ Claim 3.2. In G(n,p), for p nr/s−1, for every t = 1,...,s and for any fixed sequence of vertices ≤ U = v ,...,v , for every vertex v V U we have i 0 ⌊tr/s⌋ i ∈ \ Pr[v S (t)] nfr(tr/s)−1(1+o(1)). ∈ v0,...,v⌊tr/s⌋ ≤ Intuitively, the claim follows from two simple observations: (a) For any set of vertices S V ⊆ in G(n,p), w.h.p. the neighborhood of S has cardinality at most pn S (since the degree of every | | vertex is tightly concentrated around pn), and (b) for every vertex set S, the expected cardinality of its intersection with the neighborhood of any vertex v is at most E[S Γ(v)] p S . Applying | ∩ | ≤ | | these bounds inductively to the construction of the sets S(t) when p = nr/s−1 then implies S(t) | | ≤ nfr(tr/s) for every t. Proof (sketch). In fact, it suffices to show equality for p = nr/s−1 (since for sparser random graphs the probability can only be smaller). More precisely, for this value of p, we show: Pr[v S (t)] = nfr(tr/s)−1(1 o(1)). ∈ v0,...,v⌊tr/s⌋ ± 6 We prove the claim by induction. For i= 1, it follows by definition of G(n,p): Pr[v S (1)] = ∈ v0 p = nr/s−1. For t > 1, assume the claim holds for t 1. If the interval [(t 1)r/s,tr/s] contains − − an integer (for 1 < t s it must be (t 1)r/s ), then S(t) = S(t 1) Γ(v ). Thus, by ⌈(t−1)r/s⌉ ≤ ⌈ − ⌉ − ∩ definition of G(n,p) and the inductive hypothesis, Pr[v S (t)] = p Pr[v S (t 1)] ∈ v0,...,v⌊tr/s⌋ · ∈ v0,...,v⌊(t−1)r/s⌋ − = nr/s−1nfr((t−1)r/s)−1(1+o(1)) = nfr(tr/s)−1(1 o(1)). ± Otherwise, if the interval [(t 1)r/s,tr/s] does not contain an integer, then S(t) = Γ(S(t 1)). In − − this case, by the inductive hypothesis, the cardinality of the set S(t 1) is tightly concentrated | − | around nfr((t−1)r/s) (using Chernoff-Hoeffding bounds). If we condition on the choice of all S(t′) for t′ < t, and S(t 1) has (approximately) the above cardinality, then for every v not appearing in − the previous sets, we have Pr[v S (t)] = Pr[ u S (t 1) :(u,v) E] ∈ v0,...,v⌊tr/s⌋ ∃ ∈ v0,...,v⌊tr/s⌋ − ∈ = 1 (1 p)|S(t−1)| − − = p S(t 1)(1 o(1)) since p S(t 1) = o(1) | − | − | − | = nr/s−1nfr((t−1)r/s)(1 o(1)) ± = nfr(tr/s)−1(1 o(1)). ± Note that a more careful analysis need also bound the number of vertices participating in S(t) S(t′) for all t′ < t. Further, even in this case, tight concentration assumed above is only ∩ achieved when the expected size of the set is nΩ(1). However, this is guaranteed by the inductive hypothesis, assuming r and s are relatively prime. Now by symmetry, the same bounds can be given when constructing the candidate sets in the oppositedirection, from righttoleft(note thesymmetryof thestructure). Thus,onceall theleaves are fixed, every candidate for an internal vertex can be described, for some t [1,s 1], as the ∈ − rightmost backbone vertex in the tth prefix, as well as the leftmost backbone vertex in the (s t)th − prefix starting from the right. By Claim 3.2, the probability of this event is at most nfr(tr/s)−1nfr((s−t)r/s)−1(1+o(1)) = n−1(1+o(1)). Thus, since the (r,s)-caterpillar has s r internal vertices and r+1 leaves, it follows by standard − probabilistic arguments that, for some universal constant C > 0, the probability that total number of caterpillars for any sequence of leaves exceeds (logn)s−r is at most (s r)nr+1n−Cloglogn, which − is o(1) for any constants r,s. Now let us consider the number of (r,s)-caterpillars with a fixed set of leaves in a k-subgraph H with minimum degree at least d = k(r+ε)/s. Ignoring low-order terms (which would account for repeated leaves), the number of (r,s)-caterpillars in H (double counting each caterpillar to account for constructing it inductively once from each direction) is at least kds (since it is a tree with s edges), whereas the number of possible sequences of leaves is at most kr+1. Thus, the number of (r,s) caterpillars in H corresponding to the average sequence of r + 1 H-vertices is at least kds/kr+1 = kr+ε/kr = kε. Note that the parameters for the high probability success of the dense- versus-random distinguishing algorithm are the same as for the random planted model, giving, as before, an distinguishing ratio of O˜(n1/4) in the worst case. 7 4 An LP based algorithm for arbitrary graphs We now give a general algorithm for DkS inspired by the distinguishing algorithm in the Dense vs Random setting. For a graph G with maximum degree D = nr/s, we will use the (r,s)-caterpillar template, andkeeptrackofsetsS(t)asbefore. Wethenfixtheleaves onebyone, whilemaintaining suitable bounds on S(t). Let us start by describing the LP relaxation.2 Taking into account the simplifications from Section 2, we define a hierarchy of LPs which is satisfied by a graph which contains a subgraph of size at most k with minimum degree at least d. This hierarchy is at most as strong as the Lov´asz- Schrijver LP hierarchy based on the usual LP relaxation (and is possibly weaker). Specifically, for all integers t 1, we define DkS-LP (G,k,d) to be the set of n-dimensional vectors (y ,...y ) t 1 n ≥ satisfying: y k, and (1) i ≤ i∈V X y i,j V s.t. ij ∃{ | ∈ } i V y dy (2) ij i ∀ ∈ ≥ j∈Γ(i) X i,j V y = y (3) ij ji ∀ ∈ i,j V 0 y y 1 (4) ij i ∀ ∈ ≤ ≤ ≤ if t > 1, i Vs.t. y = 0 y /y ,...,y /y DkS-LP (G,k,d) (5) i i1 i in i t−1 ∀ ∈ 6 { }∈ Given an LP solution y , we write LP (S) = y . When the solution is clear from { i} {yi} i∈S i context, we denote the same by LP(S). We call this the LP-value of S. When the level in the P hierarchy will not be important, we will simply write DkS-LP instead of DkS-LP . A standard t argument shows that a feasible solution to DkS-LP (G,k,d) (along with all the recursively defined t solutions implied by constraint (5)) can befound in time nO(t). For completeness, we illustrate this in Appendix B Informally, we can think of the LP as giving a distribution over subsets of V, with y being the i probability that i is in a subset. Similarly y can be thought of as the probability that both i,j ij are ‘picked’. We can now think of the solution y /y : 1 j n as a distribution over subsets, ij i { ≤ ≤ } conditioned on the event that i is picked. Algorithmoutline. Theexecutionofthealgorithmfollowstheconstructionofan(r,s)-caterpillar. We perform s steps, throughout maintaining a subset S(t) of the vertices. For each t, we perform either a ‘backbone step’ or a ‘hair step’ (which we will describe shortly). In each of these steps, we will either find a dense subgraph, or extend an inductive argument that will give a lower bound on the ratio LP(S(t))/S(t). Finally, we show that if none of the steps finds a dense subgraph, then | | we reach a contradiction in the form of a violated LP constraint, namely LP(S(s)) > S(s). | | 4.1 The Algorithm Let us now describe the algorithm in detail. The algorithm will take two kinds of steps, backbone and hair, corresponding to the two types of caterpillar edges. While these steps differ in the 2Theentirealgorithm canbeexecutedwithoutsolvinganLP,byperforminganexhaustivesearchforthebestset of leaves, with runningtime comparable to that of solving theLP. Wewill elaborate on this later. 8 updates they make, both use the same procedure to search locally for a dense subgraph starting with a current candidate-set. Let us now describe this procedure. DkS-Local(S,k) Consider the bipartite subgraph induced on (S,Γ(S)). • For all k′ = 1,...,k, do the following: • – Let T be the set of k′ vertices in Γ(S) with the highest degree (into S). k′ – Take the min k′, S vertices in S with the most neighbors in T , and k′ { | |} let H (S) be the bipartite subgraph induced on this set and T . k′ k′ Output the subgraph H (S) with the largest average degree. k′ • We will analyze separately the performance of this procedure in the context of a leaf-step and that of a hair-step. We begin by relating the performance of this procedure to an LP solution. Claim 4.1. Given a set of vertices S V, and an LP solution y DkS-LP(G,k,d), let i ⊆ { } ∈ k′ = LP(Γ(S)) . Then DkS-Local(S,k) outputs a subgraph with average degree at least ⌈ ⌉ 1 y Γ(j) S . max S ,k′ · j| ∩ | {| | } j∈Γ(S) X Proof. Note that by constraint (1), k′ = LP(Γ(S)) k. Then in Procedure DkS-Local, the ⌈ ⌉ ≤ verticesinT musthaveatleast y Γ(j) S edgestoS: indeed,thesummation y Γ(j) k′ j∈Γ(S) j| ∩ | j| ∩ S can be achieved by taking 1 Γ(j) S and moving some of the weight from vertices | Pj∈Tk′ ·| ∩ | P in T to lower-degree (w.r.t. S) vertices (and perhaps throwing some of the weight away). After k′ P choosing the min k′, S vertices in S with highest degree, the remaining subgraph H (S) has k′ { | |} average degree at least min k′, S 1 { | |} y Γ(j) S . S · k′ · j| ∩ | | | j∈Γ(S) X This proves the claim. ThebackbonestepinthealgorithmfirstperformsDkS-LocalonthecurrentS,andthensetsS to beΓ(S). ThefollowinglemmagivesawaytoinductivelymaintainalowerboundonLP(S(t))/S(t) | | assuming DkS-Local does not find a sufficiently dense subgraph. Lemma 4.2. Given S V, and an LP solution y for DkS-LP(G,k,d): for any ρ 1 such that i ⊆ { } ≥ LP(S)/S ρ/d, either DkS-Local(S,k) outputs a subgraph with average degree at least ρ or we | | ≥ have dLP(S) LP(Γ(S)) . ≥ ρ Proof. By the LP constraints (4) and (2), we have y Γ(j) S y = y dLP(S). j ij ij | ∩ |≥ ≥ j∈Γ(S) j∈Γ(S)i∈Γ(j)∩S i∈S j∈Γ(i) X X X X X 9