To measure the similarity of the shape of point sets, rather than their mere closeness in space, various notions of a Hausdorff distance under translation have been investigated. Specifically, let P and Q denote point sets of n and m points, respectively, in ℝ^d. We consider the task of computing the minimum distance d(P,Q+τ) over an admissible set of translations τ ∈ T, where d(⋅, ⋅) denotes the Hausdorff distance under the L_∞-norm. As variants, we distinguish between continuous (T = ℝ^d) or discrete (T is a given finite set of t translations) as well as directed or undirected (choosing the directed or undirected Hausdorff distance for d(⋅, ⋅)). We seek to apply the paradigm of fine-grained complexity to understand the complexity of these variants, and in particular: How is the running time influenced by the dimension d, the relationship between n and m, and the specific choice of variant? As our main results, we obtain: - The asymmetric definition of the most studied variant, the continuous directed Hausdorff distance, results in an intrinsically asymmetric time complexity: While (Chan, SoCG'23) established a symmetric Õ((nm)^{d/2}) upper bound for all d ≥ 3 and proved it to be conditionally optimal for combinatorial algorithms whenever m ≤ n, we show that this lower bound does not hold for the case n ≪ m, by providing a combinatorial, almost-linear-time algorithm for d = 3 and n = m^{o(1)}. We further prove general, i.e., non-combinatorial, conditional lower bounds for d ≥ 3, in particular: (1) m^{⌊d/2⌋ - o(1)} for small n and (2) n^{d/2 - o(1)} for d = 3 and small m. - We observe that the directed and undirected case is closely related, in particular, all our lower bounds for d ≥ 3 hold for both the directed and undirected variant. A remarkable exception is the case of d = 1 for which we provide a conditional separation. Specifically, in contrast to the undirected variants being solvable in near-linear time (Rote, IPL'91), we show that the directed variants are at least as hard as the additive problem MaxConv LowerBound introduced in (Cygan, Mucha, Wegrzycki and Wlodarczyk, TALG'19). - We show that the discrete variants reduce to a variant of 3SUM for d ≤ 3. This gives a barrier in proving a tight lower bound of these variants under the Orthogonal Vectors Hypothesis (OVH); in contrast, the continuous variants admit a tight conditional lower bound under OVH in d = 2 (Bringmann, Nusser, JoCG'21). These results reveal an intricate interplay of dimensionality, symmetry and discreteness in determining the fine-grained complexity of computing Hausdorff distances under translation.

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph G = (V,E) and a pattern of length m, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in 𝒪(m |E| + N) time, where N is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length Θ(|V|). Thus, we might be able to bypass this lower bound by restricting the walk length to b-1, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into b blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the b-SMBG problem. Equi et al. [Algorithmica, 2023] showed that, if we impose no restriction on b, the existing algorithm of Amir et al. is essentially optimal for b-SMBG (again under SETH). We provide a more fine-grained classification that essentially settles the complexity of b-SMBG parameterized by b: 1) For b = 2, Pissis [SOSA 2025] already provided a simple 𝒪(m + |E|+N)-time algorithm. 2) We design a new 𝒪̃(m + |E| + N)-time algorithm for b = 3. As a direct implication of this result, the SMLG problem for b ≤ 3 (walks of length at most 2) also admits near-linear-time complexity. 3) There is no 𝒪((m |E|)^{1-ε} + N)-time combinatorial algorithm, for any b ≥ 4 and ε > 0. 4) There is an algorithm working in 𝒪(max(|V|, m)^ω+N) time, where ω is the matrix multiplication exponent, which is conditionally optimal for graphs with b ≥ 4 blocks. 5) Under SETH, no 𝒪((m |E|)^{1-ε} + N)-time algorithm exists, for any b = ω(log |V|) and ε > 0. Although our motivation is primarily of a theoretical nature, we stress that our algorithms are simple to implement. As such, they may contribute to practical advancements in applications where the SMLG problem is an important primitive, such as in the analysis of pangenome graphs.

Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with $\mathcal{O}(n\log n)$ many edges. We present significant progress towards proving that linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them to provide a simpler and more intuitive proof of the $\mathcal{O}(n\log n)$ bound. Moreover, we use our novel approach to show that a large class of temporal cliques, called edge-pivot graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivot graphs. We introduce two such graph classes and we develop novel techniques for establishing the existence of linear temporal spanners in these graph classes as well.

Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for high-stakes areas such as real estate valuation. Unfortunately, the methods applied there often exhibit a trade-off between accuracy and explainability.