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

The literature for computing the Tutte polynomial is very rich, and we make no attempt to survey it here. A recent paper of [GJ08], which shows that the Tutte polynomial is hard to even approximate for large parts of the Tutte plane, contains an overview. A list of graph classes for which subexponential time algorithms are known can be found in [BHKK08].

Results Our hardness results are based on two versions of the exponential time hypothesis. The (randomized) exponential time hypothesis (ETH) as deﬁned in [IPZ01] is that satisﬁThe Feynman quote and many other quotes describing the frustration and puzzlement of physicists around that time can be found in the copious footnotes of [Ist00].

1. Introduction ability of 3-CNF formulas cannot be computed substantially faster than by trying all

**possible assignments, i.e., it requires time exp(Ω(n)). Formally, this reads as follows:**

(ETH) There is a constant c 0 such that no randomized algorithm can decide 3-Sat in time exp(c · n) with error probability at most 3.

The second hypothesis we are using is the (deterministic) counting exponential time hypothesis, based on the counting variant of 3-Sat.

Name #3-Sat Input 3-CNF formula ϕ with n variables and m clauses.

Output The number of satisfying assignments to ϕ.

The best known algorithm for this problem runs in time O(1.6423n ) [Kut07].

(#ETH) There is a constant c 0 such that no deterministic algorithm can compute #3-Sat in time exp(c · n).

ETH trivially implies #ETH whereas the other direction is not known. By introducing the sparsiﬁcation lemma, [IPZ01] show that ETH is a robust notion in the sense that the clause width 3 and the parameter n in its deﬁnition can be replaced by d ≥ 3 and m, respectively, to get an equivalent hypothesis. The constant c may change in doing so.

We transfer the sparsiﬁcation lemma to #d-Sat and get a similar kind of robustness for #ETH, the proof of which is spelled out in §C.

** Theorem 1.8.**

Let d ≥ 3 be an integer. Then #ETH holds if and only if there is a constant c 0 such that no deterministic algorithm can solve #d-Sat time exp(c · m).

For convenience, we say that #d-Sat requires time exp(Ω(m)).

Counting Independent Sets In light of Theorem 1.8, it is natural to consider the exponential time complexity of #2-Sat. Restricted to antimonotone 2-CNF formulas, this corresponds to counting all independent sets in a given graph, which Hoﬀmann [Hof10] shows to require time exp(Ω(n/ log3 n)) under #ETH. The loss of the poly log-factor in the exponent is due to the interpolation inherent in the hardness reduction. We avoid interpolation using the isolation lemma for d-CNF formulas [CIKP03] and get an asymptotically tight lower bound, with the drawback that our lower bound only holds under the (randomized) exponential time hypothesis ETH instead of #ETH.

** Theorem 1.9.**

Counting independent sets and #2-Sat require time exp(Ω(m)) under ETH, where m is the number of edges and clauses, respectively.

We discuss the isolation technique and prove this theorem in §5.1.

The Permanent

**For a set S of rationals we deﬁne the following problems:**

Name PermS Input Square matrix A with entries from S.

Output The value of per A.

We write Perm for PermN. If B is a bipartite graph with Aij edges from the ith vertex in the left half to the jth vertex in the right half (1 ≤ i, j ≤ n), then per(A) equals the number of perfect matchings of B. Thus Perm and Perm0,1 can be viewed as counting the perfect matchings in bipartite multigraphs and bipartite simple graphs, respectively.

We express our lower bounds in terms of m, the number of non-zero entries of A.

Without loss of generality, n ≤ m, so the same bounds hold for the parameter n as well.

Note that these bounds imply that the hardest instances have roughly linear density.

** Theorem 1.10.**

(i) Perm−1,0,1 and Perm require time exp(Ω(m)) under #ETH.

(ii) Perm01 requires time exp(Ω(m/ log n)) under #ETH.

(iii) Perm01 requires time exp(Ω(m)) under ETH.

The proof of this theorem is in §5.2. For (i), we follow a standard reduction by Valiant [Val79, Pap94] but use a simple equality gadget derived from [BD07] instead of Valiant’s XOR-gadget, and we use interpolation to get rid of the negative weights. To establish (ii) we simulate edge weights w 1 by gadgets of size logarithmic in w, which increases the number of vertices and edges by a logarithmic factor. For (iii) we use the isolation lemma and the reduction from part (i), and we simulate the edge weights −1 without interpolation by replacing them with 2 and doing computation modulo 3.

The Tutte Polynomial The computational problem Tutte(x, y) is deﬁned for each pair (x, y) of rationals.

Name Tutte(x, y).

Input Undirected multigraph G with n vertices.

Output The value of T (G; x, y).

In general, parallel edges and loops are allowed; we write Tutte01 (x, y) for the special case where the input graph is simple.

Our main result is that under #ETH, Tutte(x, y) requires time exp(Ω(n)) for speciﬁc points (x, y), but the size of the bound, and the graph classes for which it holds, varies.

We summarise our results in the theorem below, see also Figure 1.1. Our reductions often give edge-exponential lower bounds, i.e., bounds in terms of the parameter m, which implies the same bounds in terms of n because m ≥ n in connected graphs.

1. Introduction

** Figure 1.1.**

: Exponential time complexity under #ETH of the Tutte plane for multigraphs (left) and simple graphs (right) in terms of n, the number of vertices. The white line y = 1 on the map is uncharted territory. The black hyperbola (x − 1)(y − 1) = 1 and the four points close to the origin are in P. Everywhere else, in the shaded regions, we prove a lower bound exponential in n, or within a polylogarithmic factor of it.

Moreover, a lower bound of exp(Ω(m/ poly log m)) together with the algorithm in time exp(O(n)) from [BHKK08] implies that worst-case instances are sparse, in the sense that m = O(n · poly log n).

Tutte01 (x, y) requires time exp(Ω(m/ log3 m)) (iv) if (x − 1)(y − 1) ∈ {0, 1} and (x, y) ∈ {(−1, −1), (−1, 0), (0, −1)}.

In an attempt to prove these results, we may ﬁrst turn to the literature, which contains a cornucopia of constructions for proving hardness of the Tutte polynomial in various models. In these arguments, a central role is played by graph transformations called thickenings and stretches. A k-thickening replaces every edge by a bundle of k edges, and a k-stretch replaces every edge by a path of k edges. This is used to ‘move’ an evaluation from one point to another. For example, if H is the 2-stretch of G then T (H; 2, 2) ∼ T (G; 4, 3 ). Thus, every algorithm for (2, 2) works also at (4, 4 ), connecting the complexity of the two points. These reductions are very well-developed in the literature, and are used in models that are immune to polynomial-size changes in the input parameters, such as #P-hardness and approximation complexity. However, we cannot always aﬀord such constructions in our setting, otherwise our bounds would

** **

**1.2. Sparse Instances of Counting Problems**

be of the form exp(Ω(n1/r )) for some constant r depending on the blowup in the proof.

In particular, the parameter n is destroyed already by a 2-stretch in a nonsparse graph.

The proofs are in §5.3. Where we can, we sample from established methods, carefully avoiding or modifying those that are not parameter-preserving. At other times we require more subtle techniques, e.g., the constructions in §5.3.3, which use graph products with graphs of polylogarithmic size instead of thickenings and stretches. Like many recent papers, we use Sokal’s multivariate version of the Tutte polynomial, which vastly simpliﬁes many of the technical details.

Consequences The permanent and Tutte polynomial are equivalent to, or generalisations of, various other graph problems, so our lower bounds under ETH and #ETH hold for these problems as well. In particular, it takes time exp(Ω(m)) to compute the following graph polynomials (for example, as a list of their coeﬃcients) for a given simple graph: the Ising partition function, the q-state Potts partition function (q = 0, 1, 2), the reliability polynomial, the chromatic polynomial, and the ﬂow polynomial. Moreover, we have exp(Ω(n)) lower bounds for the following counting problems on multigraphs: # perfect matchings, # cycle covers in digraphs, # connected spanning subgraphs, all-terminal graph reliability with given edge failure probability p 0, # nowhere-zero k-ﬂows (k = 0, ±1), and # acyclic orientations.

The lower bound for counting the number of perfect matchings holds even in bipartite graphs, where an O(1.414n ) algorithm is given by Ryser’s formula. Such algorithms are also known for general graphs [BH08a], the current best bound is O(1.619n ) [Koi09].

For simple graphs, we have exp(Ω(m)) lower bounds for # perfect matchings and # cycle covers in digraphs.

2. Preliminaries Most of our notation is standard (see [AB09, Gol08] for general and [DF99, FG06, Nie06] for parameterized complexity). We suﬃce with a review of some particular notions and notation we use.

Problems By a problem we usually mean a decision problem, i.e., deciding membership to a language L ⊆ {0, 1}∗. Apart from their bitlength |x|, instances x ∈ {0, 1}∗ often have another natural complexity parameter k(x), such as the number of vertices in the case of graph problems, or the witness length in the case of NP-problems. The function k : {0, 1}∗ → N is called parameterization and a parameterized problem is a pair (L, k).

We often write L for both the parameterized and unparameterized problem, e.g., when saying that a parameterized problem is NP-complete.

We denote the complement of L by L. The OR of a language L is the language OR(L) that consists of all tuples (x1,..., xt ) with t 0 for which there is an i ∈ [t] with xi ∈ L.

An OR-problem with arity t : N → N \ {0} is a problem OR(L) restricted to instances that satisfy the additional properties s = |x1 | = · · · = |xt | and t = t(s) for some s ∈ N.

We denote this problem by ORt (L).

Satisﬁability A d-CNF formula on the variables x1,..., xn is a conjunction of clauses where a clause is a disjunction of exactly d literals, i.e., the variables xi and their negations xi. We denote by d-Sat the problem of deciding whether a given d-CNF formula has at least one satisfying assignment, i.e., a truth assignment to its variables that makes the formula evaluate to true.

Hypergraph Problems A hypergraph G = (V (G), E(G)) consists of a ﬁnite set V (G) of vertices and a set E(G) of subsets of V (G), the (hyper)edges. A hypergraph is d-uniform if every edge has size exactly d. A vertex cover of G is a set S ⊆ V (G) that contains at least one vertex from every edge of G, and d-Vertex Cover is the problem of deciding whether, for a given d-uniform hypergraph G and integer k, there exists a vertex cover of G of size at most k. Similarly, a clique of G is a set S ⊆ V (G) all of whose subsets of size d are edges of G, and d-Clique is the problem of deciding whether, for given (G, k), there exists a clique of G of size at least k. The two problems are dual to each other, in the sense that G, the d-uniform hypergraph obtained from G by ﬂipping the presence of all edges of size d, has a clique of size k if and only if G has a vertex cover of size n − k.

Note that this transformation preserves the number of vertices.

Reductions Unless stated otherwise the reductions we consider are computable in time polynomial in the bitlength of the input. We indicate this by a superscript p in the

2. Preliminaries notation ≤p for reducibility. We consider both general reductions (also known as Turing reductions) as well as mapping reductions (also known as many-one reductions). A mapping reduction, or ≤p -reduction, from L to L is a mapping R from {0, 1}∗ to {0, 1}∗ m such that R(x) ∈ L if and only if x ∈ L.

A compression of (L, k) is a ≤p -reduction from L to some language L that maps m instances with parameter k to instances of bitlength at most g(k) for some computable function g independent of the input size. A kernelization is a compression with L = L. Note that any decidable parameterized problem that has a kernelization is ﬁxedparameter tractable, that is, it can be solved in deterministic time f (k) · poly(n) for some computable function f : The reduced instance has size at most g(k) and can be solved using any algorithm for L.

Complexity Classes The polynomial-time hierarchy PH is the union ∪i≥0 Σp, where i Σp = P, and Σp = NPΣi for i ≥ 0. We say that the polynomial-time hierarchy p 0 i+1 collapses to its ith level if PH = Σp. It is widely conjectured that the polynomial-time i hierarchy does not collapse to any level.

Given a class C of languages, we denote by coC the class {L | L ∈ C}. Apart from the ﬁrst few levels of the polynomial-time hierarchy and their co-classes, we make use of complexity classes with advice. Given a class C of languages and a function : N → N, we denote by C/ (n) the class of languages L for which there exists a language L ∈ C and a sequence a0, a1, a2,... of strings with |an | ≤ (n) such that for any input x, we have that x ∈ L if and only if x, a|x| ∈ L, where ·, · denotes a standard pairing function. We call an the advice at length n. C/ poly is a shorthand for ∪c0 C/nc. P/ poly consists exactly of the languages that can be decided by Boolean circuits of polynomial size. Similarly, NP/ poly consists exactly of the languages that can be decided by nondeterministic Boolean circuits of polynomial size. A nondeterministic circuit has two types of inputs – the actual input x and auxiliary input y. It accepts an actual input x if and only if there exists a setting of the auxiliary input y such that the circuit outputs 1 on the combined input x and y.