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

Obtaining tight bounds for H-Matching seems to be a challenging problem in general. As Theorem 1.6 shows in the case of cliques, the lower bound of O(k 2− ) implied by Theorem 1.7 is not always tight. We demonstrate that the upper bound of O(k |V (H)| ) is not always tight either. A simple argument shows that if H is a star of arbitrary size, then a kernel of size O(k 2 ) is possible, which is tight by Theorem 1.7. The examples of cliques and stars show that the exact bound on the kernel size of H-Matching for a particular H could be very far from the weak O(k |V (H)| ) upper bound or the weak O(k 2− ) lower bound (Theorem 1.7). Full understanding of this question seems to be a very challenging, yet very natural problem. The proofs of all packing-related results are in §3.5.

Techniques and Related Work At a high level our approach reﬁnes the framework developed by Bodlaender et al.

[BDFH09] to show that certain parameterized NP-hard problems are unlikely to have kernels of polynomial size. Harnik and Naor [HN06] realized the connection between their notion of lossy compression, kernelization, and PCPs for satisﬁability of general Boolean formulas, and Fortnow and Santhanam [FS08] proved the connection with the hypothesis coNP ⊆ NP/poly in the superpolynomial setting. Several authors subsequently applied the framework to prove polynomial kernel lower bounds under this hypothesis [CFM07, BTY09, DLS09, FFL+ 09, KW10, KW09, KMW10].

We develop the ﬁrst application of the framework in the polynomial setting, i.e., to problems that do have kernels of polynomial size, or more generally, oracle communication protocols of polynomial cost. Under the same hypothesis we show that problems like d-Sat, vertex cover, or set packing do not have protocols of polynomial cost of degree less than the best known. All known kernel lower bounds for ﬁxed-parameter tractable problems use, at least implicitly, the following lemma as a proxy. The lemma follows

** **

**1. Introduction**

along the lines of the proof of Fortnow and Santhanam [FS08], and we generalize it to the oracle communication model in §3.1.

** Lemma 1.1 (OR Incompressibility Lemma).**

For any NP-hard language L and polynomially bounded function t : N → N \ {0}, the problem ORt (L) does not have a compression of size O(t log t) unless coNP ⊆ NP/poly.

Here ORt (L) is the problem whose yes-instances are t-tuples of instances of L each of the same size s such that t = t(s) and at least one of the instances is a yes-instance of L. Under the assumption coNP ⊆ NP/poly, this lemma says that the problem ORt (L), seen as a parameterized problem with parameter s, does not have kernels of size O(t(s) log t(s)) even if we relax our notion of kernelization to compressions, in which the target language of the reduction may diﬀer from the source language. We review how this theorem can be used to prove conditional polynomial kernel lower bounds for the k-path problem in §2.2.

Our main result, Theorem 1.2, deals with the vertex cover problem on d-uniform hypergraphs, or equivalently, with the clique problem on such graphs, parameterized by the number of vertices. Assuming the above incompressibility lemma, the proof of this result consists of a polynomial-time mapping reduction from OR(L) to the clique problem such that t-tuples of instances of size s are mapped to instances with few vertices n = n(s, t). Then any assumed kernelization of size O(nc ) for the clique problem can be combined with this reduction to give a compression of size O(nc ) for ORt (L).

As observed by Harnik and Naor [HN06], the disjoint union of the given hypergraphs provides a reduction from OR(L) to L if L is the clique problem itself. However, the number of vertices is n = s · t, so even if c = 1, the size of the compression for OR(L) is ω(t log t), which is too much for Lemma 1.1 to apply. As a critical piece in our proof, we present a reduction from OR(3-Sat) to clique that only needs n = s · t1/d vertices. The size of the combined compression for OR(3-Sat) then goes down to O(nc ) = O (s·t1/d )c, which is O(t log t) for some suﬃciently large polynomial t(s) as long as c d.

In fact, we have two reductions for clique that yield these tight results: one is elementary and the other hinges on a graph packing that is based on high-density subsets of the integers without nontrivial arithmetic progressions of length three. For Theorem 1.7, we give a proof using the latter construction. After we developed the construction based on arithmetic progression free sets, we have learned about other applications of those sets in the theory of computing, including three-party communication protocols [CFL83], the asymptotically best known algorithm for matrix multiplication [CW90], the soundness analysis of graph tests for linearity [HW03], and lower bounds for property testing [AFKS00, Alo02, AS06, AS04, AKKR08, AS05]. The latter two applications as well as ours implicitly or explicitly rely on a connection due to Ruzsa and Szemerédi [RS78] between these subsets and dense three-partite graphs whose edges partition into triangles and that contain no other triangles. The graph packing we develop is most akin to a construction by Alon and Shapira [AS05] in the context of property testing. We refer to §4 for a more detailed discussion of the relationships.

We can generalize Lemma 1.1 to show that whenever ORt (L) has a low-cost protocol, the complement of L has short witnesses that can be veriﬁed eﬃciently with the help

** **

**1.2. Sparse Instances of Counting Problems**

of a polynomial-size advice string, i.e., L ∈ NP/poly. We refer to this generalization as the Complementary Witness Lemma and we prove it in §3.1. It involves a reﬁned analysis and generalization of the proof of Fortnow and Santhanam [FS08] that establishes the case where the protocol implements a mapping reduction to instances of bitlength bounded by some ﬁxed polynomial in s. We analyze what happens for mapping reductions without the latter restriction and we observe that the argument generalizes to our oracle communication protocol setting. Our applications of Theorem 1.1 only use oracle communication protocols that implement mapping reductions or general reductions. For the results concerned with mapping reduction, Lemma 1.1 would suﬃce. However, the setting of oracle communication protocols is more natural and allows us to prove known results in a simpler way, as we discuss in §3.6.

**1.2. Sparse Instances of Counting Problems**

The permanent of a matrix and the Tutte polynomial of a graph are central topics in the study of counting algorithms. Originally deﬁned in the combinatorics literature, they unify and

**Abstract**

many enumeration problems, including immediate questions about graphs such as computing the number of perfect matchings, spanning trees, forests, colourings, certain ﬂows and orientations, but also less obvious connections to other ﬁelds, such as link polynomials from knot theory, reliability polynomials from network theory, and (maybe most importantly) the Ising and Potts models from statistical physics.

From its deﬁnition (repeated in (1.1) below), the permanent of an n × n-matrix can be computed in O(n!n) time, and the Tutte polynomial (1.2) can be evaluated in time exponential in the number of edges. Both problems are famously #P-hard, which rules out the existence of polynomial-time algorithms under standard complexity-theoretic assumptions, but that does not mean that we have to resign ourselves to brute-force evaluation of the deﬁnition. In fact, Ryser’s famous formula [Rys63] computes the permanent with only exp(O(n)) arithmetic operations, and more recently, an algorithm with running time exp(O(n)) for n-vertex graphs has also been found [BHKK08] for the Tutte polynomial. Curiously, both of these algorithms are based on the inclusion–exclusion principle. In this thesis, we show that these algorithms cannot be signiﬁcantly improved, by providing conditional lower bounds of exp(Ω(n)) for both problems.

It is clear that #P-hardness is not the right conceptual framework for such claims, as it is unable to distinguish between diﬀerent types of super-polynomial time complexities. For example, the Tutte polynomial for planar graphs remains #P-hard, but can √ be computed in time exp(O( n)) [SIT95]. Therefore, we work under the Exponential Time Hypothesis (ETH), viz. the complexity theoretic assumption that deciding the satisﬁability of 3-CNF formulas in n variables requires time exp(Ω(n)). More speciﬁcally, we introduce #ETH, a counting analogue of ETH which models the hypothesis that counting the satisfying assignments requires time exp(Ω(n)).

1. Introduction Computing the permanent The permanent of an n × n matrix A is deﬁned as

where Sn is the set of permutations of {1,..., n}. This is similar to the determinant from linear algebra, det A = π sign(π) i Aiπ(i), the only diﬀerence is an easily computable sign for every summand. Both deﬁnitions involve a summation with n! terms, but admit much faster algorithms that are textbook material: The determinant can be computed in polynomial time using Gaussian elimination and the permanent can be computed in O(2n n) operations using Ryser’s formula.

Valiant’s celebrated #P-hardness result [Val79] for the permanent shows that no polynomial-time algorithm à la “Gaussian elimination for the permanent” can exist unless P = NP, and indeed unless P = P#P. Several unconditional lower bounds for the permanent in restricted models of computation are also known. [JS82] have shown that monotone arithmetic circuits need n(2n−1 − 1) multiplications to compute the permanent, a bound they can match with a variant of Laplace’s determinant expansion. [Raz09] has shown that multi-linear arithmetic formulas for the permanent require size exp(Ω(log2 n)). Ryser’s formula belongs to this class of formulas, but is much larger than the lower bound; no smaller construction is known. Intriguingly, the same lower bound holds for the determinant, where it is matched by a formula of size exp(O(log2 n)) due to [Ber84]. One of the consequences of this thesis is that Ryser’s formula is in some sense optimal under #ETH. In particular, no uniformly constructible, subexponential size formula such as Berkowitz’s can exist for the permanent unless #ETH fails.

A related topic is the expression of per A in terms of det f (A), where f (A) is a matrix of constants and entries from A and is typically much larger than A. This question has fascinated many mathematicians for a long time, see Agrawal’s survey [Agr06]; the best known bound on the dimension of f (A) is exp(O(n)) and it is conjectured that all such constructions require exponential size. In particular, it is an important open problem if a permanent of size n can be expressed as a determinant of size exp(O(log2 n)). We show that under #ETH, if such a matrix f (A) exists, computing f must take time exp(Ω(n)).

Computing the Tutte polynomial The Tutte polynomial, a bivariate polynomial associated with a given graph G = (V, E) with n vertices and m edges, is deﬁned as

where k(A) denotes the number of connected components of the subgraph (V, A).

Despite their uniﬁed deﬁnition (1.2), the various computational problems given by T (G; x, y) for diﬀerent points (x, y) diﬀer widely in computational complexity, as well as in the methods used to ﬁnd algorithms and lower bounds.

** **

**1.2. Sparse Instances of Counting Problems**

For example, T (G; 1, 1) equals the number of spanning trees in G, which happens to admit a polynomial time algorithm, curiously again based on Gaussian elimination.

On the other hand, the best known algorithm for computing T (G; 2, 1), the number of forests, runs in exp(O(n)) time.

Computation of the Tutte polynomial has fascinated researchers in computer science and other ﬁelds for many decades. For example, the algorithms of Onsager and Fischer from the 1940s and 1960s for computing the so-called partition function for the planar Ising model are viewed as major successes of statistical physics and theoretical chemistry;

this corresponds to computing T (G; x, y) along the hyperbola (x − 1)(y − 1) = 2 for planar G. Many serious attempts were made to extend these results to other hyperbolas or graph classes, but “after a quarter of a century and absolutely no progress”, Feynman in 1972 observed that “the exact solution for three dimensions has not yet been found”.1 The failure of theoretical physics to “solve the Potts model” and sundry other questions implicit in the computational complexity of the Tutte polynomial were explained only with Valiant’s #P-hardness programme. After a number of papers, culminating in [JVW90], the polynomial-time complexity of exactly computing the Tutte polynomial at points (x, y) is now completely understood: it is #P-hard everywhere except at those points (x, y) where a polynomial-time algorithm is known; these points consist of the hyperbola (x − 1)(y − 1) = 1 as well as the four points (1, 1), (−1, −1), (0, −1), (−1, 0).

In this thesis, we show an exp(Ω(n)) lower bound to match the exp(O(n)) algorithm from [BHKK08], which holds under #ETH everywhere except for |y| = 1. In particular, √ this establishes a gap to the planar case, which admits an exp(O( n)) algorithm [SIT95].

Our hardness results apply (though not everywhere, and sometimes with a weaker bound) even if the graphs are sparse and simple. These classes are of particular interest because most of the graphs arising from applications in statistical mechanics arise from bond structures, which are sparse and simple.

It has been known since the 1970s [Law76] that graph 3-colouring can be solved in time exp(O(n)), and this is matched by an exp(Ω(n)) lower bound under ETH [IPZ01].

Since graph 3-colouring corresponds to evaluating T at (−2, 0), the exponential time complexity for T (G; −2, 0) was thereby already understood. In particular, computing T (G; x, y) for input G and (x, y) requires vertex-exponential time, an observation that is already made in [GHN06] without explicit reference to ETH.