Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

The fine-grained complexity of computing the tutte polynomial of a linear matroid

Björklund, Andreas LU and Kaski, Petteri (2021) 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms p.2333-2345
Abstract

We show that computing the Tutte polynomial of a linear matroid of dimension k on kO(1) points over a field of kO(1) elements requires kΩ(k) time unless the #ETH-a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell et al. [ACM TALG 2014]-is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. Moreover, we also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on kO(1) points with at most three nonzero coordinates in each point's vector. These two results stand in... (More)

We show that computing the Tutte polynomial of a linear matroid of dimension k on kO(1) points over a field of kO(1) elements requires kΩ(k) time unless the #ETH-a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell et al. [ACM TALG 2014]-is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. Moreover, we also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on kO(1) points with at most three nonzero coordinates in each point's vector. These two results stand in sharp contrast to computing the Tutte polynomial of a k-vertex graph (that is, the Tutte polynomial of a graphic matroid of dimension k-which is representable in dimension k over the binary field so that every vector has exactly two nonzero coordinates), which is known to be computable in 2kkO(1) time [Björklund et al., FOCS 2008]. Our lower-bound proofs proceed in three steps: 1. a classic connection due to Crapo and Rota [1970] between the number of tuples of codewords of full support and the Tutte polynomial of the matroid associated with the code; 2. an earlier-established #ETH-hardness of counting the solutions to a bipartite (d, 2)-CSP on n vertices in do(n) time; and 3. new embeddings of such CSP instances as questions about codewords of full support in a linear code. Geometrically, our hardness results also establish that it is #ETH-hard to compute the volume of proper hyperplane chambers in time ko(k) for a given arrangement of hyperplanes through the origin of a finite k-dimensional vector space over a kO(1)-element field. We complement these lower bounds with two algorithm designs to form essentially a complexity dichotomy under #ETH. The first design computes the Tutte polynomial of a linear matroid of dimension k on kO(1) points in kO(k) arithmetic operations in the base field. The second design generalizes the Björklund et al. algorithm from the graphic case and runs in qk+1kO(1) time for linear matroids of dimension k defined over the q-element field by kO(1) points with at most two nonzero coordinates each.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
series title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
editor
Marx, Daniel
pages
13 pages
publisher
Association for Computing Machinery (ACM)
conference name
32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
conference location
Alexandria, Virtual, United States
conference dates
2021-01-10 - 2021-01-13
external identifiers
  • scopus:85097815594
ISBN
9781611976465
language
English
LU publication?
yes
id
947c1103-07d3-4cb9-84d6-f94f6acd8d23
date added to LUP
2022-01-03 12:52:33
date last changed
2022-04-27 07:00:48
@inproceedings{947c1103-07d3-4cb9-84d6-f94f6acd8d23,
  abstract     = {{<p>We show that computing the Tutte polynomial of a linear matroid of dimension k on k<sup>O</sup><sup>(1)</sup> points over a field of k<sup>O</sup><sup>(1)</sup> elements requires k<sup>Ω(</sup>k) time unless the #ETH-a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell et al. [ACM TALG 2014]-is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. Moreover, we also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on k<sup>O</sup><sup>(1)</sup> points with at most three nonzero coordinates in each point's vector. These two results stand in sharp contrast to computing the Tutte polynomial of a k-vertex graph (that is, the Tutte polynomial of a graphic matroid of dimension k-which is representable in dimension k over the binary field so that every vector has exactly two nonzero coordinates), which is known to be computable in 2<sup>k</sup>k<sup>O</sup><sup>(1)</sup> time [Björklund et al., FOCS 2008]. Our lower-bound proofs proceed in three steps: 1. a classic connection due to Crapo and Rota [1970] between the number of tuples of codewords of full support and the Tutte polynomial of the matroid associated with the code; 2. an earlier-established #ETH-hardness of counting the solutions to a bipartite (d, 2)-CSP on n vertices in d<sup>o</sup>(n) time; and 3. new embeddings of such CSP instances as questions about codewords of full support in a linear code. Geometrically, our hardness results also establish that it is #ETH-hard to compute the volume of proper hyperplane chambers in time k<sup>o</sup>(k) for a given arrangement of hyperplanes through the origin of a finite k-dimensional vector space over a k<sup>O</sup><sup>(1)</sup>-element field. We complement these lower bounds with two algorithm designs to form essentially a complexity dichotomy under #ETH. The first design computes the Tutte polynomial of a linear matroid of dimension k on k<sup>O</sup><sup>(1)</sup> points in k<sup>O</sup>(k) arithmetic operations in the base field. The second design generalizes the Björklund et al. algorithm from the graphic case and runs in q<sup>k</sup><sup>+1</sup>k<sup>O</sup><sup>(1)</sup> time for linear matroids of dimension k defined over the q-element field by k<sup>O</sup><sup>(1)</sup> points with at most two nonzero coordinates each.</p>}},
  author       = {{Björklund, Andreas and Kaski, Petteri}},
  booktitle    = {{ACM-SIAM Symposium on Discrete Algorithms, SODA 2021}},
  editor       = {{Marx, Daniel}},
  isbn         = {{9781611976465}},
  language     = {{eng}},
  pages        = {{2333--2345}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  series       = {{Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}},
  title        = {{The fine-grained complexity of computing the tutte polynomial of a linear matroid}},
  year         = {{2021}},
}