Andreas Björklund

SODA Conference 2025 Conference Paper

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

• Andreas Björklund
• Radu Curticapean
• Thore Husfeldt
• Petteri Kaski
• Kevin Pratt

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n -vertex graph can be computed deterministically in O (1. 99982 n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2 n poly( n ) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2 n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting k -colorings for small k and enumerating k -colorable subgraphs, with an extension and derandomisation of Pratt’s tensor-based algorithm for balanced three-way partitioning to the unbalanced case.

STOC Conference 2024 Conference Paper

The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True

• Andreas Björklund
• Petteri Kaski

Strassen’s asymptotic rank conjecture [ Progr. ‍Math. ‍120 ‍(1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any є>0 there exists a positive integer constant k such that no algorithm solves the k -Set Cover problem in worst-case time ((2−є) n | F |poly( n )). The k -Set Cover problem asks, given as input an n -element universe U , a family F of size-at-most- k subsets of U , and a positive integer t , whether there is a subfamily of at most t sets in F whose union is U . The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh ‍in the monograph Parameterized Algorithms [Springer, ‍2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlstr'om ‍[CCC ‍2012, ACM ‍Trans. ‍Algorithms ‍2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS ‍2019], in this scenario we would also get an ((2−δ) n )-time randomized algorithm for some constant δ>0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given n -vertex directed graph has a Hamiltonian cycle. At a fine-grained level, our results do not need the full strength of the asymptotic rank conjecture; it suffices that the conclusion of the conjecture holds approximately for a single 7× 7× 7 tensor.

STOC Conference 2022 Conference Paper

The shortest even cycle problem is tractable

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski

SODA Conference 2021 Conference Paper

The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid

• Andreas Björklund
• Petteri Kaski

We show that computing the Tutte polynomial of a linear matroid of dimension k on k O (1) points over a field of k O (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 k O (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 2 k k O (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 d o ( 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 o ( k ) for a given arrangement of hyperplanes through the origin of a finite k -dimensional vector space over a k O (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 k O (1) points in k O ( 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 k +1 k O (1) time for linear matroids of dimension k defined over the q -element field by k O (1) points with at most two nonzero coordinates each.

SODA Conference 2014 Conference Paper

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time

• Andreas Björklund
• Petteri Kaski
• Lukasz Kowalik

Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k /2 edges in an n -vertex graph in time n k /2+ O (1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via n st /2+ O (1) -time algorithms for counting t -tuples of pairwise disjoint sets drawn from a given family of s -sized subsets of an n -element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω( n ⌊ st /2⌋ ) and Ω( n ⌊ k /2⌋ ) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meet-in-the-middle” exponent st /2 can be beaten and give an algorithm that counts in time n 0. 4547 st + O (1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an n -vertex graph in n 0. 4547 k +2 p + O (1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.

FOCS Conference 2013 Conference Paper

The Parity of Directed Hamiltonian Cycles

• Andreas Björklund
• Thore Husfeldt

We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1. 619n) time and polynomial space. For bipartite graphs, we give a 1. 5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.

SODA Conference 2012 Conference Paper

Counting perfect matchings as fast as Ryser

• Andreas Björklund

We show that there is a polynomial space algorithm that counts the number of perfect matchings in an n -vertex graph in O *(2 n /2 ) ⊂ O (1. 415 n ) time. ( O *( f ( n )) suppresses functions polylogarithmic in f ( n )). The previously fastest algorithms for the problem was the exponential space O *(((1 + √5)/2) n ) ⊂ O (1. 619 n ) time algorithm by Koivisto, and for polynomial space, the O (1. 942 n ) time algorithm by Nederlof. Our new algorithm's runtime matches up to polynomial factors that of Ryser's 1963 algorithm for bipartite graphs. We present our algorithm in the more general setting of computing the hafnian over an arbitrary ring, analogously to Ryser's algorithm for permanent computation. We also give a simple argument why the general exact set cover counting problem over a slightly superpolynomial sized family of subsets of an n element ground set cannot be solved in O *(2 (1 − ε 1 ) n ) time for any ∊ 1 > 0 unless there are O *(2 (1 − ε 1 ) n ) time algorithms for computing an n × n 0/1 matrix permanent, for some ∊ 2 > 0 depending only on ∊ 1.

SODA Conference 2012 Conference Paper

Fast zeta transforms for lattices with few irreducibles

• Andreas Björklund
• Mikko Koivisto
• Thore Husfeldt
• Jesper Nederlof
• Petteri Kaski
• Pekka Parviainen

SODA Conference 2012 Conference Paper

Shortest cycle through specified elements

• Andreas Björklund
• Thore Husfeldt
• Nina Taslaman

We give a randomized algorithm that finds a shortest simple cycle through a given set of k vertices or edges in an n -vertex undirected graph in time 2 k n O (1).

FOCS Conference 2010 Conference Paper

Determinant Sums for Undirected Hamiltonicity

• Andreas Björklund

We present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running in O* (1. 657 n ) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the O*(2 n ) bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to O* (1. 414 n ) time. Both the bipartite and the general algorithm can be implemented to use space polynomial in n. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for k-Path (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers (Björklund STACS 2010) to evaluate it.

FOCS Conference 2008 Conference Paper

Computing the Tutte Polynomial in Vertex-Exponential Time

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski
• Mikko Koivisto

The deletion–contraction algorithm is perhapsthe most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin–Kasteleyn in statistical physics. Prior to this work, deletion–contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial—and hence, all the aforementioned invariants and more—of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.

STOC Conference 2007 Conference Paper

Fourier meets möbius: fast subset convolution

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski
• Mikko Koivisto

We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of an n -element set n , compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n 2 2 n ) additions and multiplications, substanti y improving upon the straightforward O(3 n ) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2 n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2 n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2 k n 2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3 k n + 2 k n 2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2 n )-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).

FOCS Conference 2006 Conference Paper

Inclusion--Exclusion Algorithms for Counting Set Partitions

• Andreas Björklund
• Thore Husfeldt

Given a set U with n elements and a family of subsets S sube 2 U we show how to count the number of k-partitions S 1 cup. .. cup S k = U into subsets S i isin S in time 2 n n O(1). The only assumption on S is that it can be enumerated in time 2 n n O(1). In effect we get exact algorithms in time 2 n n O(1) for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3 n n O(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2. 2461 n ) and polynomial space. For domatic number, we present a version that runs in time O(2. 8718 n ). Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and [(1 + epsi)chi(G)] in time O(1. 2209 n + 2. 2461 e-epsi n)