# «Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

Thus, (G, s) ∈ d-Clique if and only if (ϕ1,..., ϕt ) ∈ OR(3-Sat). Since G and s are computable in time polynomial in the bitlength of (ϕ1,..., ϕt ) and |V (G)| ≤ 3|V (P )| ≤ O s · max(s, t1/d+o(1) ), we have established the ≤p -reductions claimed in Lemma 3.2.

m Proof based on AP-free sets This section contains the original proof of Lemma 3.2 that appeared in [DvM10]. It is based on high-density subsets of the integers that do not contain arithmetic progressions of length three.

The reduction works by ﬁrst applying a standard translation of the t individual 3Sat-instances ϕ1,..., ϕt, say of size s, into equivalent d-Clique-instances consisting of d-uniform hypergraphs G1,..., Gt on 3s vertices each, such that Gi has a clique of size s if and only if ϕi is satisﬁable. All that is left then is to turn these t instances into a single instance of d-Clique which is positive if and only if at least one of the t instances is. If we take G as the disjoint union of the Gi ’s, then G is a d-uniform hypergraph that has a clique of size s if and only if at least one of the Gi ’s has a clique of size s.

However, this G contains n = 3s · t vertices, which is too many for our purposes. In order to do better, we need to pack the graphs Gi more tightly while maintaining the properties required of the reduction. The following almost-optimal packing of cliques is

3. Communicating Instances of Hard Problems the critical ingredient in the construction and allows us to achieve the almost-optimal lower bounds given in Theorem 1.2.

** Lemma 3.3 (Packing Lemma).**

For any integers p ≥ d ≥ 2 and t 0 there exists an p-partite d-uniform hypergraph P on O p · max(p, t1/d+o(1) ) vertices such that (i) the hyperedges of P partition into t cliques K1,..., Kt on p vertices each, and (ii) P contains no cliques on p vertices other than the Ki ’s.

Furthermore, for any ﬁxed d, the hypergraph P and the Ki ’s can be constructed in time polynomial in p and t.

Condition (i) in Lemma 3.3 formalizes the notion of a packing. The part that P contains the t cliques Ki ensures the completeness of the reduction, i.e., that G has a clique of size p := s if at least one of the Gi ’s does. The part that the Ki ’s are edge-disjoint and condition (ii) guarantee the soundness of the reduction, i.e., that G has a clique of size s only if at least one of the Gi ’s does.

We defer the proof of Lemma 3.3 to §4. Using it as sketched above we obtain an alternative reduction for Lemma 3.2.

Proof (of Lemma 3.2). Let ϕ1,..., ϕt be the t instances of 3-Sat. Without loss of generality, assume that each formula has exactly p = s clauses, each consisting of a sequence of 3 literals. Let P and K1,..., Kt be the hypergraphs provided by Lemma 3.3.

Along the lines of the standard reduction from 3-Sat to 2-Clique by Karp [Kar72], we ﬁrst translate the 3-CNF formulas ϕi into d-uniform hypergraphs Gi on the vertex sets V (Ki ) × [3]. For each i, we identify the elements of V (Ki ) × [3] with (positions of) literals of ϕi : The ﬁrst component selects a clause from ϕi and the second component selects a literal from the clause. We let Gi be the d-uniform hypergraph with as edges all subsets e ⊆ V (Ki ) × [3] of size d such that no two elements of e correspond to the same clause ϕi or represent complementary literals. Note that each such e induces a satisfying assignment of the conjunction of the d clauses touched by e, and that Gi has a clique of size s if and only if ϕi is satisﬁable.

Let G be the union of the Gi ’s, that is, the graph with V (G) = i∈[t] V (Gi ) ⊆ V (P ) × [3] and E(G) = i∈[t] E(Gi ). If ϕi has a satisfying assignment, then Gi has a clique of size s and so has G. For the other direction, let K be a clique of size s in G. The projection K of K onto the ﬁrst component is a clique of size s in P. By property (ii) of Lemma 3.3, K = Ki for some i ∈ [t]. Moreover, by property (i) of Lemma 3.3, the projections of E(Gi ) and E(Gj ) for j = i are disjoint. It follows that K is a clique of size s in Gi, and therefore ϕi is satisﬁable.

Thus, (G, s) ∈ d-Clique if and only if (ϕ1,..., ϕt ) ∈ OR(3-Sat). Since G and s are computable in time polynomial in the bitlength of (ϕ1,..., ϕt ) and |V (G)| ≤ 3|V (P )| ≤ O s · max(s, t1/d+o(1) ), we have established the ≤p -reductions claimed in Lemma 3.2.

m

3.3. Satisﬁability Theorem 1.1, our tight oracle communication lower bound for d-Sat parameterized by the number of variables of the formula, immediately follows from Theorem 1.2 and the next lemma.

Proof. Let (G, k) be an n-vertex instance of d-Vertex Cover. The following d-CNF

**formula on variables xv for v ∈ V (G) has as satisfying assignments precisely the characteristic vectors of vertex covers of G:**

Using at most O(n) new variables, we construct a 3-CNF formula ψ that is satisﬁed by all assignments in which at most k distinct xv are set to true. Then ϕ ∧ ψ is satisﬁable if and only if G has a vertex cover of size at most k.

For the construction of ψ, we use a Boolean circuit of constant fan-in that has at most O(n) gates and checks whether at most k of the n input variables are set to true.

Such circuits can be constructed for any symmetric function in time polynomial in n when given oracle access to the function [Weg87, Theorem 4.1]. Once we have that circuit, we construct ψ in a standard way by introducing a new variable for each gate, and letting ψ be the conjunction of clauses that express the correct behavior of each of the gates, and the clause stipulating that the output gate is set.

Proof (of Theorem 1.1). Suppose there exists an oracle communication protocol of cost O(nd− ) for n-variable instances of d-Sat. We combine the reduction from Lemma 3.4 with the former and obtain an protocol of cost O(nd− ) for n-vertex instances of dVertex Cover. By Theorem 1.2, this implies that coNP ⊆ NP/poly.

The following corollary to Theorem 1.1 embodies the consequences for sparsiﬁcation, kernelization, and lossy compression.

Corollary 3.1. Let d ≥ 3 be an integer. If coNP ⊆ NP/poly, there is no polynomialtime reduction from d-Sat to any problem that makes at most O(nb ) queries and only queries strings of bitlength O(nc ), where b and c are any nonnegative reals with b+c d.

In particular, under the hypothesis that coNP ⊆ NP/poly, Corollary 3.1 implies that ≤p -reductions cannot reduce the density of n-variable d-Sat instances to O(nc ) clauses m for any constant c below the trivial c = d. This is in contrast to the subexponential-time level: The sparsiﬁcation lemma of [IPZ01] gives a reduction which, on input an n-variable d-CNF formula and a rational 0, runs in time 2 n · poly(n) and makes 2 n nonadaptive queries, each of which are d-CNF formulas with at most f (d, ) · n clauses. The best known bound on the sparsiﬁcation constant f (d, ) is (d/ )3d [CIP06]. The sparsiﬁcation

** **

**3. Communicating Instances of Hard Problems**

lemma implies that sparse instances of d-Sat are hard under subexponential-time reductions while Corollary 3.1 suggests that such a result is impossible under ≤p -reductions.

m Interpretations of Corollary 3.1 in terms of kernelization and lossy compression follow along the same lines.

Another consequence of Theorem 1.1 deals with the size of probabilistically checkable proofs for satisﬁability. Recall that Dinur [Din07] constructed such PCPs of size O(s · poly log s), where s denotes the bitlength of the formula. Based on a connection due to Harnik and Naor [HN06] between PCPs and lossy compression, Fortnow and Santhanam [FS08] showed that satisﬁability of Boolean formulas does not have PCPs of size bounded by a polynomial in the number of variables only, unless coNP ⊆ NP/poly.

Plugging in our lower bound for d-Sat into their argument shows that d-Sat does not have q-query PCPs of size O(nd/q− ) unless coNP ⊆ NP/poly. Since q ≥ 3 this bound is not tight. Using a diﬀerent argument and exploiting the fact that Theorem 1.1 also holds for conondeterministic protocols, we can close the gap between the upper and lower bound.

Corollary 3.2. Let d ≥ 3 be an integer and a positive real. If coNP ⊆ NP/poly, then d-Sat does not have probabilistically checkable proofs of bitlength O(nd− ) where n denotes the number of variables of the input formula.

Proof. Suppose that d-Sat has PCPs of size s = O(nc ) that make q nonadaptive queries, where c and q are constants. We claim that this implies a conondeterministic multivalued mapping reduction from d-Sat to q-Sat that maps formulas on n variables to instances of bitlength O(nc log n) in the following sense: There exists a nondeterministic polynomial-time Turing machine M which outputs a q-CNF formula on each computation path (where the formula may depend on the input and the computation path) such that (i) if the input is in d-SAT then every output is in q-SAT, and (ii) otherwise at least one output is not in q-SAT. For c d, Theorem 1.1 then shows that coNP ⊆ NP/poly.

All that remains is to argue the claim. For a given formula ϕ on n variables, introduce s new variables y, namely one for each bit position in a candidate PCP of size s. If the PCP system reads at most q bits of the proof, each condition the PCP system checks can be expressed eﬃciently as a q-CNF. By picking a condition according to the distribution of the PCP system and a clause of the corresponding q-CNF formula uniformly at random, we obtain a polynomial-time randomized procedure that produces a q-clause on the variables y with the property that if ϕ is satisﬁable, then all q-clauses produced are simultaneously satisﬁable, and otherwise less than a constant fraction ρ 1 is. By averaging, the latter implies that for every collection of candidate PCPs of size s for an unsatisﬁable input ϕ, there exists a produced q-clause that is violated by more than a fraction 1 − ρ of the collection. Since there are 2s candidate PCPs of size s in total, this means that there is a set of s/ log(1/ρ) produced q-clauses that cannot be satisﬁed by any PCP of size s. The reduction nondeterministically guesses s/ log(1/ρ) many q-clauses that are produced by the PCP system on input ϕ, and outputs their conjunction. The conjunction has bitlength O(nc log n), is always satisﬁable if ϕ is, and is not satisﬁable on at least one computation path otherwise.

It is straightforward to obtain applications similar to Corollaries 3.1 and 3.2 for dVertex Cover and other problems.

3.4. Covering Problems Combinatorial covering problems are problems in which we are given a graph and a pattern, and we want to ﬁnd few vertices that cover each occurrence of the pattern in the graph. Put diﬀerently, we want to know whether it is possible to delete k vertices from the graph such that no copies of the respective pattern remain. Clearly d-Vertex Cover is of that kind, since we want to ﬁnd k vertices whose removal leaves a graph without edges. A natural parameter for d-Vertex Cover and covering problems in general is the size k of the deletion set. We investigate the consequences of Theorem 1.2 for this parameterization of covering problems, ﬁrst for the case d = 2, i.e., for standard graphs, and then for d-uniform hypergraphs for general d.

Result for Standard Graphs We consider the following generalization of the vertex cover problem. Recall that a graph property is a predicate on graphs that is invariant under graph isomorphism.

Deﬁnition 3.1 (Vertex Deletion). Fix a graph property Π. The Π-Vertex Deletion problem is to decide, for a given graph G and integer k, whether there exists a subset S of at most k vertices such that G \ S satisﬁes Π.

We say that a graph property Π is inherited by subgraphs if, whenever a graph G satisﬁes Π, every subgraph of G also satisﬁes Π. The following natural graph problems are special cases of Π-Vertex Deletion for a graph property Π that is inherited by subgraphs.

• Vertex Cover: Can we delete k vertices to destroy all edges?

• Feedback Vertex Set: Can we delete k vertices to destroy all cycles?

• Bounded-Degree Deletion: Can we delete k vertices to get a maximum degree of d?

• Non-Planar Deletion: Can we delete k vertices to make the graph planar?

• Can we delete k vertices to make the graph embeddable into some surface?

• Can we delete k vertices to make the graph exclude any ﬁxed set of minors?

As mentioned in the introduction, if only ﬁnitely many graphs satisfy Π or if all graphs satisfy Π, Π-Vertex Deletion is trivially decidable in polynomial time. For all other graph properties Π that are inherited by subgraphs, Theorem 1.3 implies that Π-Vertex Deletion does not have kernels with O(k 2− ) edges unless coNP ⊆ NP/poly.

3. Communicating Instances of Hard Problems

** Figure 3.1.**

: Replacement of an edge e = {u, v} in the transformation from G to G in the proof of Lemma 3.5. (a) Feedback Vertex Set. (b) Bounded-Degree Deletion. (c) The general case.

We now prove Theorem 1.3 by constructing a ≤p -reduction from Vertex Cover m to Π-Vertex Deletion that blows up the size of the deletion set by no more than a constant factor. In order to develop some intuition, we ﬁrst consider the standard reduction from Vertex Cover to Feedback Vertex Set [Kar72]. The reduction replaces every edge e of a Vertex Cover-instance G by a cycle of length three using an additional new vertex, as depicted in Figure 3.1a. Let us denote the resulting graph by G. Since every cycle in G contains two vertices that are adjacent in G, every vertex cover of G hits every cycle of G and therefore is a feedback vertex set of G. Conversely, every feedback vertex set of G contains a vertex of every triangle we created, and can therefore be turned into a vertex cover of G of at most the same size. Thus, G has a vertex cover of size k if and only if G has a feedback vertex set of size k.