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

For (ii), we have to get rid of weights larger than 1. Let Ga be one query of the last reduction. Again we assume that a ≤ n and that weights = 1 are only allowed at loop edges. We replace every edge of weight a by the gadget that is drawn in Figure 5.2, and call this new unweighted graph G. It can be checked easily that the gadget indeed simulates a weight of a (parallel paths correspond to addition, serial edges to multiplication), i.e., per G = per Ga. Unfortunately, the reduction increases the number of edges by a superconstant factor: The number of edges of G is m(G ) ≤ (m+n log a) ≤ O(m+n log n).

5. Exponential Time Counting Complexity

But since m(G )/ log m(G ) ≤ O(m), the reduction implies that (ii).

For (iii), we assume that ETH holds. Theorem 5.1 gives that Unique 3-Sat cannot be computed in time exp(o(m)). Now we apply the ﬁrst reduction of (i) to a formula ϕ which is promised to have at most one satisfying assignment. Then the number per G = (−2)i · #Sat(ϕ) is either 0 or (−2)i. In G, we replace each edge of weight −1 by a gadget of weight 2 ≡ −1 mod 3 and similarly get that (per G mod 3) is (0 mod 3) or (4i mod 3). Since (4i mod 3) = 0, we can distinguish the case in which ϕ is unsatisﬁable from the case in which ϕ has exactly one satisfying assignment.

5.3. The Tutte Polynomial In this section, we prove Theorem 1.11, our hardness results for evaluating the Tutte polynomial. For quick reference, we state the propositions in which the individual results are proved and the techniques used in each case.

** Theorem 1.11 (restated).**

Let (x, y) ∈ Q2. Under #ETH, Tutte(x, y) requires time exp(Ω(n)) (i) if (x − 1)(y − 1) = 1 and y ∈ {0, ±1}, ( Proposition 5.3 in §5.3.2; stretching and thickening )

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)}.

( Proposition 5.4 in §5.3.3; inﬂation with Theta graphs )

see [Sok05, eq. (2.26)].

The Ising Hyperbola We begin with the case q = 2.

Proposition 5.1. Computing the coeﬃcients of the polynomial w → Z(G; 2, w) for given simple graph G requires time exp(Ω(m)) under #ETH.

Proof. The reduction is from #MaxCut and well-known, see, e.g., [JS93, Theorem 15].

Name #MaxCut Input Simple undirected graph G.

Output The number of maximum cuts.

A maximum cut is a set C ⊆ V (G) that maximizes the number |E(C, C)| of edges of G that cross the cut. By the Fortuin–Kasteleyn identity [Sok05, Theorem 2.3], one can express Z(G; 2, w) for G = (V, E) as

Here the Iverson bracket [P ] is 1 if P is true and is 0 if P is false. The sets σ −1 (1) and σ −1 (−1) deﬁne a cut in G, so we can write the above expression as

Now, the coeﬃcient of (1 + w)m−c in Z(G; 2, w) is the number of cuts in G of size c. In particular, after some interpolation, we can compute the number of maximum cuts in G from the coeﬃcients of w → Z(G; 2, w). But as we observe in Appendix D, #MaxCut requires time exp(Ω(m)) under #ETH.

** **

**5. Exponential Time Counting Complexity**

The Multivariate Tutte Polynomial For other q, in particular nonintegers, it is simpler to work with a multivariate formulation of the Tutte polynomial due to Fortuin and Kasteleyn [FK72]. We use Sokal’s deﬁnition [Sok05]: Let G = (V, E) be an undirected graph whose edge weights are given by a function w : E → Q. Then Z(G; q, w) = (5.2) q k(A) w(e).

A⊆E e∈A If w is single-valued, in the sense that w(e) = w for all e ∈ E, we recover Z(G; q, w).

The conceptual strength of the multivariate perspective is that it turns the Tutte polynomial’s second variable y, suitably transformed, into an edge weight of the graph.

In particular, the multivariate formulation allows the graph to have diﬀerent weights on diﬀerent edges, which turns out to be a dramatic technical simpliﬁcation even when, as in the present work, we are ultimately interested in the single-valued case.

Sokal’s polynomial vanishes at q = 0, so we sometimes use the polynomial

For ﬁxed G and q, this is a polynomial in w of degree at most m.

** Lemma 5.1.**

Let q be a rational number with q ∈ {1, 2}. Computing the coeﬃcients of the polynomial w → Z0 (G; q, w), with w as in (5.4), for a given simple graph G requires time exp(Ω(m)) under #ETH. Moreover, this is true even if |T | = 3.

Proof. In Appendix D, we argue that a standard reduction from #MaxCut already implies that the problem #3-Terminal MinCut requires time exp(Ω(m)) under #ETH.

Name #3-Terminal MinCut Input Simple undirected graph G = (V, E) with three distinguished vertices (“terminals”) t1, t2, t3 ∈ V.

Output The number of edge subsets A ⊆ E of minimal size that separate t1 from t2, t2 from t3, and t3 from t1.

We ﬁrst show that the second term of (5.6) vanishes. Consider an edge subset A ∈ A and assume without loss of generality that it connects the terminals t1 and t2. Consider B ⊆ T, and let B = B ⊕ {t1 t2 }, so that B is the same as B except for t1 t2. Then the contributions of A ∪ B and A ∪ B cancel: First, k(A ∪ B) equals k(A ∪ B ) because t1 and t2 are connected through A already, so the presence or absence of the edge t1 t2 makes no diﬀerence. Second, (−1)|B| equals −(−1)|B |.

We proceed to simplify the ﬁrst term of (5.6). The edges in B only ever connect vertices in T, and for A ∈ A, each of these lies in a separate component of (V, A), so

The edge subsets A ∈ A are exactly the complements of the 3-terminal cuts in G.

Now consider the family C of minimal 3-terminal cuts, all of size c. The sets E − A in C are exactly the sets A of size m − c in A, and by minimality, k(A) = 3. Thus,

Thus, if we could compute the coeﬃcients d0,..., dm of w → Q−1 Z0 (G; q, w), then we could determine the smallest c so that dm−c = 0 and return dm−c = |C |/Q, the number of 3-terminal mincuts.

General Hyperbolas We want to use Lemma 5.1 to show that computing the coeﬃcients of the univariate Tutte polynomial at any ﬁxed q ∈ {1, 2} is hard. For this, we need to get rid of negative weights and reduce to a single-valued weight function. In [GJ08], this is done by thickenings and stretches, which we have to avoid. Since the number of edges with a negative weight is small (in fact, 3), we can use another tool: deletion–contraction.

A deletion–contraction identity expresses a function of the graph G in terms of two graphs G − e and G/e, where G − e arises from G by deleting the edge e ( → ) and G/e arises from G by contracting the edge e ( → ) that is, deleting it and identifying its endpoints (so any remaining edges between these two endpoints become loops).

It is known [Sok05, eq. (4.6)] that

An edge e is a bridge of G if deleting e from G increases the number of connected

**components. The above gives a deletion–contraction identity for Z0 as well:**

Proposition 5.2. Let q be a rational number with q ∈ {1, 2}. Computing the coeﬃcients / of the polynomial v → Z0 (G; q, v) for a given simple graph G requires time exp(Ω(m)) under #ETH.

By (5.3), this proposition also holds for Z instead of Z0 when q ∈ {0, 1, 2}.

Proof. Let G = (V, E) be a graph as in the previous lemma, with three edges T = {e1, e2, e3 } of weight −1. The given reduction actually uses the restriction that G =

(V, E \T ) is connected, so we can assume that this is the case. Thus, none of the T -edges is a bridge, so three applications of (5.8) to delete and contract these edges, gives

where for each C ⊆ {1, 2, 3}, the graph GC is constructed from G by removing e1, e2, e3 as follows: If i ∈ C then ei is contracted, otherwise it is deleted. In any case, the edges of T have disappeared and remaining edges of GC are in one-to-one correspondence with the edges in E; especially, they all have the same weight w, so Z0 (GC ; q, w) = Z0 (GC ; q, w).

The resulting GC are not necessarily simple, because the contracted edges from T may have been part of a triangle and may have produced a loop. (In fact, investigating the details of the previous lemma, we can see that this is indeed the case.) Thus we construct the simple graph GC from GC by subdividing every edge into a 3-path. This operation, known as a 3-stretch, is known to largely preserve the value of Z and Z0 (see [Sok04] for the former and [GJ08] for the latter). In particular,

5.3.2. Individual Points for Multigraphs If we allow graphs to have multiple edges, we can use thickening and interpolation, one of the original strategies of [JVW90], for relocating the hardness result for hyperbolas from Proposition 5.1 and Proposition 5.2 to individual points in the Tutte plane. For most points, this gives us tight bounds in terms of n, the number of vertices, but not for points with y ∈ {0, ±1}, where thickening fails completely.

We recall the thickening identities for the Tutte polynomial. The k-thickening of G is the graph Gk in which all edges have been replaced by k parallel edges. One can show [Sok05, (4.21)] that, with wk = (1 + w)k − 1,

It is easy to transfer this result to the Tutte polynomial T using (5.1), yielding special cases of Brylawski’s well-known graph transformation rules.

5. Exponential Time Counting Complexity We use interpolation and obtain Theorem 1.11 (i) for y = 0 from the following.

Proposition 5.3. Let (q, w) ∈ Q2 with w ∈ {0, −1, −2} and q = 1. Computing Z(G; q, w) for a given graph G (not necessarily simple) requires time exp(Ω(n)) under #ETH.

Proof. We observe that the values wk = (1 + w)k − 1 are all distinct for k = 0, 1,..., m.

Thus, the k-thickenings Gk of G give rise to m + 1 diﬀerent weight shifts, the evaluations of which, Z(G; q, wk ), can be obtained from Z(Gk ; q, w) using (5.10). Thus, with oracle access to G → Z(G ; q, w), we can compute the coeﬃcients of the polynomial v → Z(G; q, v) in polynomial time for any given G. By Proposition 5.1 and Proposition 5.2, doing so requires time exp(Ω(n)) under #ETH. Since the number of vertices is n in each Gk, computing G → Z(G ; q, w) requires time exp(Ω(n)) under #ETH.

The proof of Theorem 1.11 (ii) uses Linial’s well-known reduction for the chromatic polynomial [Lin86], and is deferred to Proposition D.1 in Appendix D.

5.3.3. Individual Points for Simple Graphs In this section we show that most points (x, y) of the Tutte plane are as hard as the entire hyperbola on which they lie, even for sparse, simple graphs. The drawback of our method is that we lose a polylogarithmic factor in the exponent of the lower bound.

The results are particularly interesting for the points on the line y = −1, for which we know no other good exponential lower bounds under #ETH, even in more general graph classes. We remark that the points (−1, −1), (0, −1), and ( 1, −1) on this line are known to admit a polynomial-time algorithm, and indeed our hardness result does not apply here.

Graph inﬂations We use the graph theoretic version of Brylawski’s tensor product for matroids [Bry82].

We found the following terminology more intuitive in our setting.

Deﬁnition 5.1 (Graph inﬂation). Let H be a 2-terminal undirected graph. For any undirected graph G = (V, E), an H-inﬂation of G, denoted G ⊗ H, is obtained by replacing every edge xy ∈ E by (a fresh copy of) H, identifying x with one of the terminals of H and y with the other.

If H is not symmetric with respect to its two terminals, then the graph G ⊗ H need not be unique since there are in general two non-isomorphic ways two replace an edge xy by H. For us this diﬀerence does not matter since the resulting Tutte polynomials turn out to be the same; in fact, in any graph one can remove a maximal biconnected component and reinsert it in the other direction without changing the Tutte polynomial, an operation that is called the Whitney twist. Thus we choose G ⊗ H arbitrarily among the graphs that satisfy the condition in the deﬁnition above. Graph inﬂation is not commutative and Sokal uses the notation GH.

** **

**5.3. The Tutte Polynomial**

If H is a simple path of k edges, G ⊗ H gives the usual k-stretch of G, and a bundle of k parallel edges results in a k-thickening. What makes graph inﬂations so useful in the study of Tutte polynomials is that the Tutte polynomial of G ⊗ H can be expressed in terms of the Tutte polynomials of G and H, so that Z(G ⊗ H; q, w) ∼ Z(G; q, w ) for some ‘shifted’ weight w.

For ﬁxed rational points (q, w), we want to use interpolation to prove the hardness of computing Z(G; q, w) for a given graph G. The basic idea is to ﬁnd a suitable class of graphs {Hi }, such that we can compute the coeﬃcients of the monovariate polynomial v → Z(G; q, v) for given G and q by interpolation from suﬃciently many evaluations of Z(G; q, wi ) ∼ Z(G ⊗ Hi ; q, w). For this, we need that the number of diﬀerent weight shifts {wi } provided by the graph class {Hi } is at least |E(G)| + 1, one more than the degree of the polynomial.

This lemma can be derived from Sokal’s series and parallel reduction rules for Z using a straightforward calculation. Since all edge weights are the same, the result can also be established from the classical Tutte polynomial via the series and parallel reduction rules in [JVW90], but the calculation would be slightly more laborious.

We now show that the class of Theta graphs provides a rich enough spectrum of weight shifts to allow for interpolation.

** Lemma 5.3.**