Search: onr:"swepub:oai:lup.lub.lu.se:947c1103-07d3-4cb9-84d6-f94f6acd8d23" >
The fine-grained co...
The fine-grained complexity of computing the tutte polynomial of a linear matroid
-
- Björklund, Andreas (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Kaski, Petteri (author)
- Aalto University
-
Marx, Daniel (editor)
-
(creator_code:org_t)
- 2021
- 2021
- English 13 s.
-
In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. - 9781611976465 ; , s. 2333-2345
- Related links:
-
https://lup.lub.lu.s...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database