Karl Bringmann

Karl Bringmann, Nick Fischer, Yanheng Wang

The subgraph isomorphism problem and its generalizations such as conjunctive queries, where some nodes are projected, are among the most fundamental problems in graph algorithms and database theory. In this paper, we study the listing and enumeration variants of these problems and present two main results. (1) We present the first algorithms for enumerating projected trees with polynomial preprocessing time ($\widetilde{O}(n^{17.42})$) and polylogarithmic delay ($\mathrm{polylog}(n)$). Prior to this work, all algorithms in the literature required time $Ω(n^{Ω(k)} + t)$ or $t \cdot n^{Ω(1)}$ to list all copies of a $k$-node tree with projections, where $t$ is the number of solutions. Our result generalizes to arbitrary projected hypergraphs, achieving enumeration in preprocessing time $\widetilde{O}(m^{17.42 \cdot \mathrm{subw}(H)})$ and polylogarithmic delay, where $\mathrm{subw}(H)$ is the submodular width of the pattern hypergraph $H$. We heavily rely on fast (rectangular and output-sensitive) matrix multiplication, which we complement by fine-grained lower bounds indicating that any algorithm beating time $Ω(n^{Ω(k)} + t)$ must rely on fast matrix multiplication. (2) As our second main result, we present a generic enumeration-to-listing reduction, establishing that listing and enumeration are equivalent under natural assumptions. For (colored) subgraph isomorphism, our reduction transforms any listing algorithm running in time $O(f(n,m) + t \cdot g(n,m))$ into an enumeration algorithm with preprocessing time $O((f(n,m)+g(n,m)+m) \log^2 n)$ and delay $O(g(n,m))$. We utilize this equivalence as a tool for proving our first main result, and we expect that our generic reduction will find many future applications.

Karl Bringmann, Danny Hermelin, Tomohiro Koana et al.

The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion times, and each machine follows a fixed priority order such as Smith's Rule or Jackson's Rule. For the basic objectives $Pm||\sum w_jC_j$, $Pm||L_{\max}$, and $Pm||\sum w_jU_j$, it gives running times $O(P^{m-1}n)$, $O(P^{m-1}n)$, and $O(P^mn)$, respectively, where $P$ is the total processing time. Recent SETH-based lower bounds indicate that the dependence on $P$ is essentially optimal, but they do not rule out improved dependence on the maximum processing time $p_{\max}$. We give the first major speedup of the Lawler-Moore recurrence. Our main ingredients are a new state-pruning method and a swapping argument based on an additive-combinatorial lemma. We prove that, whenever this swap does not increase the objective value, there exists an optimal schedule in which, for every prefix of jobs, the load difference between any two machines is at most $4p_{\max}^2$. This lets us prune redundant states throughout the dynamic program, replacing the dependence on $P$ by a dependence on $p_{\max}^2$. We show that the swap is non-increasing for all three objectives above. Hence $Pm||\sum w_jC_j$ and $Pm||L_{\max}$ admit algorithms with running time $O(p_{\max}^{2m-2}n)$, while $Pm||\sum w_jU_j$ can be solved in time $O(p_{\max}^{2m-2}Pn)\le O(p_{\max}^{2m-1}n^2)$. These bounds strictly improve the original Lawler-Moore runtimes whenever $p_{\max}=o(\sqrt{P})$. In particular, for $Pm||\sum w_jC_j$ and $Pm||L_{\max}$, we obtain the first near-linear-time algorithms when processing times are polylogarithmic in $n$.

Lotte Blank, Karl Bringmann, Parinya Chalermsook et al.

In the (continuous) Euclidean $k$-center problem, given $n$ points in $\mathbb{R}^d$ and an integer $k$, the goal is to find $k$ center points in $\mathbb{R}^d$ that minimize the maximum Euclidean distance from any input point to its closest center. In this paper, we establish conditional lower bounds for this problem in constant dimensions in two settings. $\bullet$ Parameterized by $k$: Assuming the Exponential Time Hypothesis (ETH), we show that there is no $f(k)n^{o(k^{1-1/d})}$-time algorithm for the Euclidean $k$-center problem. This result shows that the algorithm of Agarwal and Procopiuc [SODA 1998; Algorithmica 2002] is essentially optimal. Furthermore, our lower bound rules out any $(1+\varepsilon)$-approximation algorithm running in time $(k/\varepsilon)^{o(k^{1-1/d})}n^{O(1)}$, thereby establishing near-optimality of the corresponding approximation scheme by the same authors. $\bullet$ Small $k$: Assuming the 3-SUM hypothesis, we prove that for any $\varepsilon>0$ there is no $O(n^{2-\varepsilon})$-time algorithm for the Euclidean $2$-center problem in $\mathbb{R}^3$. This settles an open question posed by Agarwal, Ben Avraham, and Sharir [SoCG 2010; Computational Geometry 2013]. In addition, under the same hypothesis, we prove that for any $\varepsilon > 0$, the Euclidean $6$-center problem in $\mathbb{R}^2$ also admits no $O(n^{2-\varepsilon})$-time algorithm. The technical core of all our proofs is a novel geometric embedding of a system of linear equations. We construct a point set where each variable corresponds to a specific collection of points, and the geometric structure ensures that a small-radius clustering is possible if and only if the system has a valid solution.

Karl Bringmann, Anita Dürr, Karol Węgrzycki

Bin Packing with $k$ bins is a fundamental optimisation problem in which we are given a set of $n$ integers and a capacity $T$ and the goal is to partition the set into $k$ subsets, each of total sum at most $T$. Bin Packing is NP-hard already for $k=2$ and a textbook dynamic programming algorithm solves it in pseudopolynomial time $\mathcal O(n T^{k-1})$. Jansen, Kratsch, Marx, and Schlotter [JCSS'13] proved that this time cannot be improved to $(nT)^{o(k / \log k)}$ assuming the Exponential Time Hypothesis (ETH). Their result has become an important building block, explaining the hardness of many problems in parameterised complexity. Note that their result is one log-factor short of being tight. In this paper, we prove a tight ETH-based lower bound for Bin Packing, ruling out time $2^{o(n)} T^{o(k)}$. This answers an open problem of Jansen et al. and yields improved lower bounds for many applications in parameterised complexity. Since Bin Packing is an example of multi-machine scheduling, it is natural to next study other scheduling problems. We prove tight lower bounds based on the Strong Exponential Time Hypothesis (SETH) for several classic $k$-machine scheduling problems, including makespan minimisation with release dates ($P_k|r_j|C_{\max}$), minimizing the number of tardy jobs ($P_k||ΣU_j$), and minimizing the weighted sum of completion times ($P_k || Σw_j C_j$). For all these problems, we rule out time $2^{o(n)} T^{k-1-\varepsilon}$ for any $\varepsilon > 0$ assuming SETH, where $T$ is the total processing time; this matches classic $n^{\mathcal O(1)} T^{k-1}$-time algorithms from the 60s and 70s. Moreover, we rule out time $2^{o(n)} T^{k-\varepsilon}$ for minimizing the total processing time of tardy jobs ($P_k||Σp_jU_j$), which matches a classic $\mathcal O(n T^{k})$-time algorithm and answers an open problem of Fischer and Wennmann [TheoretiCS'25].

Amir Abboud, Arturs Backurs, Karl Bringmann et al.

To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size $N$ down to size $n \ll N$, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process? In this paper we consider lossless compression schemes, and ask if we can run our computations on the compressed data as efficiently as if the original data was that small. That is, if an operation has time complexity $T(\rm{inputsize})$, can we perform it on the compressed representation in time $T(n)$ rather than $T(N)$? We consider the most basic linear algebra operations: inner product, matrix-vector multiplication, and matrix multiplication. In particular, given two compressed vectors, can we compute their inner product in time $O(n)$? Or perhaps we must decompress first and then multiply, spending $Ω(N)$ time? The answer depends on the compression scheme. While for simple ones such as Run-Length-Encoding (RLE) the inner product can be done in $O(n)$ time, we prove that this is impossible for compressions from a richer class: essentially $n^2$ or even larger runtimes are needed in the worst case (under complexity assumptions). This is the class of grammar-compressions containing most popular methods such as the Lempel-Ziv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.

Frank Ban, Vijay Bhattiprolu, Karl Bringmann et al.

A number of recent works have studied algorithms for entrywise $\ell_p$-low rank approximation, namely, algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$), output a rank-$k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j}|A_{i,j}-B_{i,j}|^p$ when $p > 0$; and $\|A-B\|_0=\sum_{i,j}[A_{i,j}\neq B_{i,j}]$ for $p=0$. On the algorithmic side, for $p \in (0,2)$, we give the first $(1+ε)$-approximation algorithm running in time $n^{\text{poly}(k/ε)}$. Further, for $p = 0$, we give the first almost-linear time approximation scheme for what we call the Generalized Binary $\ell_0$-Rank-$k$ problem. Our algorithm computes $(1+ε)$-approximation in time $(1/ε)^{2^{O(k)}/ε^{2}} \cdot nd^{1+o(1)}$. On the hardness of approximation side, for $p \in (1,2)$, assuming the Small Set Expansion Hypothesis and the Exponential Time Hypothesis (ETH), we show that there exists $δ:= δ(α) > 0$ such that the entrywise $\ell_p$-Rank-$k$ problem has no $α$-approximation algorithm running in time $2^{k^δ}$.

Karl Bringmann, Pavel Kolev, David P. Woodruff

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which $\|A'-A\|_0$ is minimized. Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries. This NP-hard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For $k > 1$, we show how to find, in poly$(mn)$ time for every $k$, a rank $O(k \log(n/k))$ matrix $A'$ for which $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \mathrm{OPT}$. To the best of our knowledge, this is the first algorithm with provable guarantees for the $\ell_0$-Low Rank Approximation Problem for $k > 1$, even for bicriteria algorithms. For the well-studied case when $k = 1$, we give a $(2+ε)$-approximation in {\it sublinear time}, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a $(1+O(ψ))$-approximation in sublinear time, where $ψ= \mathrm{OPT}/\lVert A\rVert_0$. For small $ψ$, our approximation factor is $1+o(1)$.