Hardness of Approximation Between P and NP. Aviad Rubinstein

Чтение книги онлайн.

СКАЧАТЬ A key step in the reduction is to consider subsets of variables; then by the birthday paradox any two subsets are likely to share at least one variable (hence the name “birthday repetition”).

      1.2.1 Densest k -Subgraph

      k-CLIQUE is one of the most fundamental problems in computer science: given a graph, decide whether it has a fully connected induced subgraph on k vertices. Since it was proven NP-complete by Karp [1972], extensive research has investigated the complexity of its relaxations.

      We consider two natural relaxations of k-CLIQUE that have received significant attention from both algorithmic and complexity communities: The first one is to relax the “k” requirement, i.e., looking for a smaller subgraph: Given an n-vertex graph G containing a clique of size k, find a clique of size at least δk for some parameter 0 < δ < 1.

      The second natural relaxation is to relax the “Clique” requirement, replacing it with the more modest goal of finding a subgraph that is almost a clique: Given an n-vertex graph G containing a clique of size k, find an induced subgraph of G of size k with (edge) density at least 1 − ε, for some parameter 0 < ε < 1.

      The first relaxation has been a motivating example throughout a long line of research that laid the foundations for NP-hardness of approximation [Arora and Safra 1998, Arora et al. 1998, Feige et al. 1996, Håstad 1999, Khot 2001, Zuckerman 2007]. In particular, we now know that it is NP-hard to distinguish between a graph that has a clique of size k, and a graph whose largest induced clique is of size at most k′ = δk, where δ = 1/n^1−ε [Zuckerman 2007]. Until our work, the computational complexity of the second relaxation remained largely open. There are a couple of (very different) quasi-polynomial algorithms that guarantee finding a (1 − ε)-dense k-subgraph in every graph containing a k-clique: the meta-algorithm by Barman, which we outlined above, and an older algorithm due to Feige and Seltser [1997], but nothing non-trivial was known about hardness of approximation.

      In Chapter 12 we prove that, assuming ETH, even if one makes both relaxations the problem remains intractable. In particular, even if the graph contains a clique of size k, it takes quasi-polynomial time to find a (1 − ε)-dense δk-subgraph, for constant ε > 0 and δ = o(1).

       1.2.2 Community Detection

      Identifying communities is a central graph-theoretic problem with important applications to sociology and marketing (when applied to social networks), biology and bioinformatics (when applied to protein interaction networks), and more (see, e.g., Fortunato’s classic survey [Fortunato 2010]). Defining what exactly is a community remains an interesting problem on its own (see Arora et al. [2012] and Borgs et al. [2016] for excellent treatment from a theoretical perspective). Ultimately, there is no single “right” definition, and the precise meaning of community should be different for social networks and protein interaction networks.

      In Chapter 13 we focus on the algorithmic questions arising from one of the simplest and most canonical definitions, which has been considered by several theoretical computer scientists [Arora et al. 2012, Balcan et al. 2013, Braverman et al. 2017, Mishra et al. 2008].

       Definition 1.2

      (α, β)-community. Given an undirected graph G = (V, E), an (α, β)-community is a subset S ⊆ V that satisfies:

      Strong ties inside the community. For every v ∈ S, |{v} × S| ⋂ E ≥ α. |S|; and

      Weak ties to nodes outside the community. For every u ∉ S, |{u} × S| ∩ E ≤ β. |S|.

      This problem has been considered by several researchers before: Mishra et al. [2008] gave a polynomial-time algorithm for finding (α, β)-communities that contain a vertex with very few neighbors outside the community. Balcan et al. [2013] give a polynomial-time algorithm for enumerating (α, β)-communities in the special case where the degree of every node is Ω(n). Arora et al. [2012] consider several semi-random models where the edges inside the community are generated at random, according to the expected degree model. For the general case, the latter paper by Arora et al. gave a simple quasi-polynomial (n^{O(log n)}) time for detecting (α, β)-communities whenever α − β is at least some positive constant. (Their algorithm is essentially identical to the meta-algorithm for bilinear optimization that we outlined above.)

      We show that, for every constants α > β ∈ (0,1], community detection requires quasi-polynomial time (assuming ETH). For example, when α = 1 and β = 0.01, this means that we can hide a clique C, such that every single vertex not in C is connected to at most 1% of C. Our main result is actually a much stronger inapproximability: even in the presence of a (1, o(1))-community, finding any (β + o(1), β)-community is hard.

      Unlike all quasi-polynomial approximation schemes mentioned above, Arora et al.’s algorithm has the unique property that it can also exactly count all the (α, β)-communities. Our second result is that counting even the number of (1, o(1))-communities requires quasi-polynomial time. A nice feature of this result is that we can base it on the much weaker #ETH assumption, which asserts that counting the satisfying assignment for a 3-SAT instance requires time 2^Ω(n). (Note, for example, that #ETH is likely to be true even if P = NP.)

       1.2.3 VC and Littlestone’s Dimensions

      A common and essential assumption in learning theory is that the concepts we want to learn come from a nice, simple concept class, or (in the agnostic case) that they can at least be approximated by a concept from a simple class. When the concept class is sufficiently simple, there is hope for good (i.e., sample-efficient and low-error) learning algorithms.

      There are many different ways to measure the simplicity of a concept class. The most influential measure of simplicity is the VC Dimension [Vapnik and Chervonenkis 1971], which captures learning in the Probably Almost Correct (PAC) model. We also consider Littlestone’s Dimension [Littlestone 1987], which corresponds to minimizing mistakes in online learning (see Section 2.5 for definitions). When either dimension is small, there are algorithms that exploit the simplicity of the class, to obtain good learning guarantees.

      In Chapter 14 we consider the algorithmic challenge of computing either dimension. In particular, we study the most optimistic setting, where the entire universe and concept class are given as explicit input (a binary matrix whose (x, c)-th entry is 1 iff element x belongs to concept c). In this model, both dimensions can be computed in quasi-polynomial time. Interestingly, the algorithm does not go through the bilinear optimization problem; instead, it exploits the fact that for concept class C, both dimensions are bounded by log |C|. Two decades ago, it was shown that quasi-polynomial time is indeed necessary for both dimensions [Frances and Litman 1998, Papadimitriou and Yannakakis 1996]. The computational intractability of computing the (VC, Littlestone’s) dimension of a concept class suggests that even in cases where a simple structure exists, it may be inaccessible to computationally bounded СКАЧАТЬ