Thore Husfeldt

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 2022 Conference Paper

The shortest even cycle problem is tractable

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski

STOC Conference 2018 Conference Paper

Extensor-coding

• Cornelius Brand
• Holger Dell
• Thore Husfeldt

We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± ε. Our algorithm runs in time ε −2 4 k ( n + m ) poly( k ). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2 k ·poly( n ) time algorithm to find a k -path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k -multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.

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

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

I&C Journal 2004 Journal Article

Dynamic nested brackets

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

We consider the problem of maintaining a string of n brackets `('or `)' under the operation reverse(i) that changes the ith bracket from `(' to `)' or vice versa, and returns `yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(logn/loglogn) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Ω(logn/loglogn) per operation in the cell probe model.

SODA Conference 2001 Conference Paper

A cell probe lower bound for dynamic nearest-neighbor searching

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

FOCS Conference 1998 Conference Paper

Marked Ancestor Problems

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

Consider a rooted tree whose nodes can be in two states: marked or unmarked. The marked ancestor problem is to maintain a data structure with the following operations: mark(v) marks node v: unmark(v) removes any marks from node v; firstmarked(v) returns the first marked node on the path from v to the root. We show tight upper and lower bounds for the marked ancestor problem. The lower bounds are proved in the cell probe model, the algorithms run on a unit-cost RAM. As easy corollaries we prove (often optimal) lower bounds on a number of problems. These include planar range searching, including the existential or emptiness problem, priority search trees static tree union-find, and several problems from dynamic computational geometry, including segment intersection, interval maintenance, and ray shooting in the plane. Our upper bounds improve algorithms from various fields, including coloured ancestor problems and maintenance of balanced parentheses.