Paweł Gawrychowski

Paweł Gawrychowski, Marcin Knapik

We consider the problem of enumerating, for a given directed graph $G=(V,E)$ and a node $r\in V$, all directed spanning trees of $G$ rooted at $r$. For undirected graphs, the corresponding problem of enumerating all spanning trees has received considerable attention, culminating in the algorithm of Kapoor and Ramesh [SICOMP 1995] working in $\mathcal{O}(n+m+N)$ time, where $N, n, m$ denote the number of spanning trees, vertices, and edges of $G$, respectively. In the area of enumeration algorithms, this is known as Constant Amortised Time, or CAT. To achieve only constant time per each spanning tree, the algorithm outputs the relative change between the subsequent spanning trees instead of the whole spanning trees themselves. The natural generalization to enumerating all directed spanning trees has been already considered by Gabow and Myers [SICOMP 1978], who provided an $\mathcal{O}(n+m+Nm)$ time algorithm. This time complexity has been improved upon a couple of times, and in 1998 Uno introduced the framework of trimming and balancing that allowed him to obtain an $\mathcal{O}(n+m\log n+N\log^{2}n)$ time algorithm for this problem. By plugging in later results it is immediate to improve the time complexity to $\mathcal{O}(n+m+N\log n)$, but achieving the optimal bound of $\mathcal{O}(n+m+N)$ seems problematic within this framework. In this paper, we show how to enumerate all directed spanning trees in $\mathcal{O}(n+m+N)$ time and $\mathcal{O}(n+m)$ space, matching the time bound for undirected graphs. Our improvement is obtained by designing a purely graph-theoretical characterization of graphs with very few directed spanning trees, and using their structure to speed up the algorithm.

Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert et al.

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model. Here, one is given read-only access to a (typically short) reference string $R$ of length $m$, while a text $T$ arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) $T$ that occurs in $R$. We show a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.