Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations $τ$ and $π$, the pattern matching problem (PPM) asks whether $τ$ contains $π$. This problem arises in various contexts in computer science and statistics and has been studied extensively in exact-, parameterized-, approximate-, property-testing- and other formulations. In this paper, we study pattern matching in a streaming setting, when the input $τ$ is revealed sequentially, one element at a time. There is extensive work on the space complexity of various statistics in streams of integers. The novelty of our setting is that the input stream is a permutation, which allows inferring some information about future inputs. Our algorithms crucially take advantage of this fact, while existing lower bound techniques become difficult to apply. We show that the complexity of the problem changes dramatically depending on the pattern $π$. The space requirement is: $Θ(k\log{n})$ for the monotone patterns $π= 12\dots k$, or $π= k\dots21$, $O(\sqrt{n\log{n}})$ for $π\in \{312,132\}$, $O(\sqrt{n} \log n)$ for $π\in \{231,213\}$, and $\widetildeΘ_π(n)$ for all other $π$. If $τ$ is an arbitrary sequence of integers (not necessary a permutation), we show that the complexity is $\widetildeΘ_π(n)$ in all except the first (monotone) cases.

We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size n under edge deletions, weight updates, and a certain information-retrieval query. Both problems can be solved in 𝒪(log n) time per update/query using standard dynamic forest data structures like top trees - even if additionally edge insertions are allowed. We investigate whether the deletion-only problem can be solved faster. First, we consider tree-sum queries, where we ask for the sum of vertex weights in one of the connected components (i.e., trees) in the forest. We give a data structure with 𝒪(n) preprocessing time and 𝒪(log^* n) time per operation, based on a micro-macro tree decomposition (Alstrup et al., 1997). If the forest is unweighted (i.e., all weights are 1 and cannot be changed), then the operation time can be improved to 𝒪(1). Additionally, we give an asymptotically universally optimal algorithm. More specifically, our algorithm works in the group model, and processes m operations on an initial forest F in running time 𝒪(OPT(F, m)). Here OPT(F, m) is the number of weight additions and subtractions that a best possible algorithm performs to handle a worst-case instance for a fixed initial forest F and a fixed number m of operations. We achieve this with a combination of the aforementioned decomposition technique, precomputation of optimal data structures for very small instances, and some insights into the behavior of OPT. Note that even the worst-case complexity of this algorithm remains unknown to us. Second, we consider subtree-sum queries. Here, the forest is rooted, and a query subtree-sum(v) returns the sum of weights in the subtree rooted at v. An easy reduction from the well-known prefix sum problem shows that the general, weighted version of the problem requires Θ(n log n) time for n operations. Interestingly, we prove that the Ω(n log n) complexity lower bound still holds even if weight updates are disallowed. On the other hand, we show that the unweighted version can be solved with 𝒪((log n)/(log log n)) time per operation, and this is tight.

The classical comparison-based sorting problem asks us to find the underlying total ordering of a given set of elements, where we can only access the elements via comparisons. In this paper, we study a restricted version, where, as a hint, a set T of possible total orderings is given, usually in some compressed form. Recently, an algorithm called topological heapsort with optimal running time was found for case where T is the set of topological orderings of a given directed acyclic graph, or, equivalently, T is the set of linear extensions of a partial ordering [Haeupler et al. 2024]. We show that a simple generalization of topological heapsort is applicable to a much broader class of restricted sorting problems, where T corresponds to a given antimatroid. As a consequence, we obtain optimal algorithms for the following restricted sorting problems, where the allowed total orders are … - … restricted by a given set of monotone precedence formulas; - … the perfect elimination orders of a given chordal graph; or - … the possible vertex search orders of a given connected rooted graph.

A dynamic forest data structure maintains a forest (and associated data like edge weights) under edge insertions and deletions. Dynamic forests are widely used to solve online and offline graph problems. Well-known examples of dynamic forest data structures are link-cut trees [28] and top trees [4], both of which need O(log n) time per operation. While top trees are more flexible and arguably easier to use, link-cut trees are faster in practice [31].

Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complexity of optimization problems. In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding. The best known bound to date is 2α(n)(1+o(1)) recently obtained by Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024); here n is the BST size and α(·) the inverse-Ackermann function. In this paper we resolve the conjecture, showing a tight (1) bound. This indicates a barrier to dynamic optimality: any candidate online BST (e.g., splay trees or greedy trees) must match this optimum, but current analysis techniques only give superconstant bounds. More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures. To illustrate this, we show that when the input avoids an arbitrary, fixed, a priori unknown pattern, one can efficiently compute: (1) a k-server solution of n requests from a unit interval, with total cost n(1/logk), in contrast to the worst-case Θ(n/k) bound, and (2) a traveling salesman tour of n points from a unit box, of length (logn), in contrast to the worst-case Θ(√n) bound; similar results hold for the euclidean minimum spanning tree, Steiner tree, and nearest-neighbor graphs. We show both results to be tight. Our techniques build on the Marcus-Tardos proof of the Stanley-Wilf conjecture, and on the recently emerging concept of twin-width.

Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a path. An optimal BST of size $n$ can be computed for a given distribution of queries in $O(n^2)$ time [Knuth 1971] and centroid BSTs provide a nearly-optimal alternative, computable in $O(n)$ time [Mehlhorn 1977]. By contrast, optimal STTs are not known to be computable in polynomial time, and the fastest constant-approximation algorithm runs in $O(n^3)$ time [Berendsohn, Kozma 2022]. Centroid trees can be defined for STTs analogously to BSTs, and they have been used in a wide range of algorithmic applications. In the unweighted case (i.e., for a uniform distribution of queries), a centroid tree can be computed in $O(n)$ time [Brodal et al. 2001; Della Giustina et al. 2019]. These algorithms, however, do not readily extend to the weighted case. Moreover, no approximation guarantees were previously known for centroid trees in either the unweighted or weighted cases. In this paper we revisit centroid trees in a general, weighted setting, and we settle both the algorithmic complexity of constructing them, and the quality of their approximation. For constructing a weighted centroid tree, we give an output-sensitive $O(n\log h)\subseteq O(n\log n)$ time algorithm, where $h$ is the height of the resulting centroid tree. If the weights are of polynomial complexity, the running time is $O(n\log\log n)$. We show these bounds to be optimal, in a general decision tree model of computation. For approximation, we prove that the cost of a centroid tree is at most twice the optimum, and this guarantee is best possible, both in the weighted and unweighted cases. We also give tight, fine-grained bounds on the approximation-ratio for bounded-degree trees and on the approximation-ratio of more general $α$-centroid trees.

Group testing is a well-studied approach for identifying t defective items in a set X of m items, by testing appropriately chosen subsets of X. In classical group testing any subset of X can be tested, and for $t \in {\mathcal{O}}(1)$ the optimal number of (non-adaptive) tests is known to be Θ(logm).In this work we consider a novel geometric setting for group testing, where the items are points in Euclidean space and the tests are axis-parallel boxes (hyperrectangles), corresponding to the scenario where tests are defined by parameter-ranges (say, according to physical measurements). We present upper and lower bounds on the required number of tests in this setting, observing that in contrast to the unrestricted, combinatorial case, the bounds are polynomial in m. For instance, we show that with two parameters, identifying a defective pair of items requires Ω(m3/5) tests, and there exist configurations for which ${\mathcal{O}}\left({{m^{2/3}}}\right)$ tests are sufficient, whereas to identify a single defective item Θ(m1/2) tests are always necessary and sometimes sufficient. Perhaps most interestingly, our work brings to the study of group testing a set of techniques from extremal combinatorics.

We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given $d$, we ask for the largest value of $n$, denoted $R_f(d)$, for which there exists a fixed-point-free labeling of $\overset{\tiny\leftrightarrow}{K}_n$. Determining $R_f(d)$ for all $d >0$ is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra, who proved that $d \leq R_f(d) \leq d^4+d$ and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound $R_f(d) \leq d^{2 + o(1)}$, yielding an efficient ${(1-\varepsilon)}$-EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$; this improves the bound of $O(n^{0.8})$ of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. Additionally, we prove the stronger upper bound $2d-2$, in the case where all edge-labels are permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$, was recently considered by Alon and Krivelevich and by Mészáros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.

Search trees on trees (STTs) are a far-reaching generalization of binary search trees (BSTs), allowing the efficient exploration of tree-structured domains. (BSTs are the special case in which the underlying domain is a path.) Trees on trees have been extensively studied under various guises in computer science and discrete mathematics. Recently Bose, Cardinal, Iacono, Koumoutsos, and Langerman (SODA 2020) considered adaptive STTs and observed that, apart from notable exceptions, the machinery developed for BSTs in the past decades does not readily transfer to STTs. In particular, they asked whether the optimal STT can be efficiently computed or approximated (by analogy to Knuth's algorithm for optimal BSTs), and whether natural self-adjusting BSTs such as Splay trees (Sleator, Tarjan, 1983) can be extended to this more general setting. We answer both questions affirmatively. First, we show that a -approximation of an optimal size-n STT for a given search distribution can be computed in time (n2t + 1) for all integers t ≥ 1. Second, we identify a broad family of STTs with linear rotation-distance, allowing the generalization of Splay trees to the STT setting. We show that our generalized Splay satisfies a static optimality theorem, asymptotically matching the cost of the optimal STT in an online fashion, i.e. without knowledge of the search distribution. Our results suggest an extension of the dynamic optimality conjecture for Splay trees to the broader setting of trees on trees.

Abstract Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of lengthncontains a given pattern of lengthk. In this work we give two new algorithms for this well-studied problem, one whose running time is $$n^{k/4 + o(k)}$$ nk/4+o(k) , and a polynomial-space algorithm whose running time is the better of $$O(1.6181^n)$$ O(1.6181n) and $$O(n^{k/2 + 1})$$ O(nk/2+1) . These results improve the earlier best bounds of $$n^{0.47k + o(k)}$$ n0.47k+o(k) and $$O(1.79^n)$$ O(1.79n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when $$k \in \varOmega (\log {n})$$ k∈Ω(logn) . We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens ofconstraint-satisfaction. Our algorithms can alsocount, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time $$f(k) \cdot n^{o(k/\log {k})}$$ f(k)·no(k/logk) would contradict theexponential-time hypothesis(ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing(4321-avoiding) and 3-decreasing(1234-avoiding) permutations can, in some sense,embedarbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.