Solon P. Pissis

The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly. This reduction employs the notion of de Bruijn graph \(G=(V,E)\) of order \( k \) over an alphabet \(\Sigma\) . A single Eulerian trail in \( G \) represents a candidate genome reconstruction. Bernardini et al. have also introduced the complementary idea in data privacy [ALENEX 2020] based on \( z \) -anonymity. Let \( S \) be a private string that we would like to release, preventing, however, its full reconstruction. For a privacy threshold \(z \gt 0\) , we compute the largest \( k \) for which there exist at least \( z \) Eulerian trails in the order- \( k \) de Bruijn graph of \( S \) , and release a string \(S^{\prime}\) obtained via a random Eulerian trail. The pressing question is: How hard is it to reconstruct a best string from a de Bruijn graph given a function that models domain knowledge? One natural model uses a function that maps every length- \( k \) string to an interval of positions where it may occur in the reconstructed string. By the above reduction to de Bruijn graphs, the latter function translates into a function \( c \) mapping every edge to an interval where it may occur in an Eulerian trail. This gives rise to the following basic problem on graphs: Given an instance \((G,c)\) , can we efficiently compute an Eulerian trail respecting \( c \) ? Hannenhalli et al. [CABIOS 1996] formalized this problem and showed that it is \(\mathsf{NP}\) -complete. Ben-Dor et al. [J. Comput. Biol. 2002] showed that it is \(\mathsf{NP}\) -complete, even on de Bruijn graphs with \(|\Sigma|=4\) . In this work, we settle the lower-bound side of this problem by showing that finding a \( c \) -respecting Eulerian trail in de Bruijn graphs over alphabets of size 2 is \(\mathsf{NP}\) -complete. We then shift our focus to parametrization aiming to capture the quality of our domain knowledge in the complexity. Ben-Dor et al. developed an algorithm to solve the problem on de Bruijn graphs in \(\mathcal{O}(m\cdot w^{1.5}4^{w})\) time, where \(m=|E|\) and \( w \) is the maximum interval length over all edges in \( E \) . Bumpus and Meeks [Algorithmica 2023] later rediscovered the same algorithm on temporal graphs, which highlights the relevance of this problem in other contexts. Our central contribution is showing how combinatorial insights lead to exponential-time improvements over the state-of-the-art algorithm. In particular, for the important class of de Bruijn graphs, we develop an algorithm parametrized by \(w(\log w+1)/(k-1)\) : for a de Bruijn graph of order \( k \) , it runs in \(\mathcal{O}(mw\cdot 2^{\frac{w(\log w+1)}{k-1}})\) time. Our result improves on the state of the art by roughly an exponent of \((\log w+1)/(k-1)\) . The existing algorithms have a natural interpretation for string reconstruction: when for each length- \( k \) string, we know a small range of positions it must lie in, string reconstruction can be solved in linear time. Our improved algorithm shows that it is enough when the range of positions is small relative to \( k \) . We then generalize both the existing and our novel \(\mathsf{FPT}\) algorithm by allowing the cost at every position of an interval to vary. In this optimization version, our hardness result translates into inapproximability and the \(\mathsf{FPT}\) algorithms work with a slight extension. Surprisingly, even in this more general setting, we extend the \(\mathsf{FPT}\) algorithms to count and enumerate the min-cost Eulerian trails. The counting result has direct applications in the data privacy framework of Bernardini et al.

Sparse suffix sorting is the problem of sorting $$b=o(n)$$ b = o ( n ) suffixes of a string of length n . Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures; direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure; fast in the sense that they run in $$\mathcal {O}(n\log b)$$ O ( n log b ) time, in the worst case, or in $$\mathcal {O}(n)$$ O ( n ) time, when the total number of suffixes with an LCP value greater than $$2^{\lfloor \log \frac{n}{b} \rfloor + 1}-1$$ 2 ⌊ log n b ⌋ + 1 - 1 is in $$\mathcal {O}(b/\log b)$$ O ( b / log b ) , matching the time of optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et al., SODA 2020]; and small in the sense that they can be implemented using only $$8b+o(b)$$ 8 b + o ( b ) machine words. Our algorithms are non-trivial space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in $$\mathcal {O}(n\log b)$$ O ( n log b ) time [STACS 2014]. We provide extensive experiments to justify our claims on simplicity and on efficiency. A preliminary version of this paper appeared in the proceedings of LATIN 2024.

In the classic Longest Common Substring (LCS) problem, we are given two strings \( S \) and \( T \) of total length \( n \) over an alphabet of size \(\sigma\) , and we are asked to find a longest string occurring as a fragment of both \( S \) and \( T \) . Weiner, in his seminal paper that introduced the suffix tree, presented an \(\mathcal{O}(n\log\sigma)\) -time algorithm for the LCS problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an \(\mathcal{O}(n)\) -time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in \(\mathcal{O}(n\log\sigma/\log n)\) space and read in \(\mathcal{O}(n\log\sigma/\log n)\) time. We show that we can compute an LCS of two strings in time \(\mathcal{O}(n\log\sigma/\sqrt{\log n})\) in the word RAM model, which is sublinear in \( n \) if \(\sigma=2^{o(\sqrt{\log n})}\) (in particular, if \(\sigma=\mathcal{O}(1)\) ), using optimal space \(\mathcal{O}(n\log\sigma/\log n)\) . In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. The same complexity can be achieved for computing an LCS of \(\lambda=\mathcal{O}(\sqrt{\log n}/\log\log n)\) input strings of total length \( n \) . We then lift our ideas to the problem of computing a \( k \) -mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of \( S \) that occurs in \( T \) with at most \( k \) mismatches. Flouri et al. showed how to compute a 1-mismatch LCS in \(\mathcal{O}(n\log n)\) time [IPL 2015]. Thankachan et al. extended this result to computing a \( k \) -mismatch LCS in \(\mathcal{O}(n\log^{k}n)\) time for \(k=\mathcal{O}(1)\) [J. Comput. Biol. 2016]. We show an \(\mathcal{O}(n\log^{k-0.5}n)\) -time algorithm, for any constant integer \(k > 0\) and irrespective of the alphabet size, using \(\mathcal{O}(n)\) space as the previous approaches. We thus notably break through the well-known \(n\log^{k}n\) barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. for string indexing with \( k \) errors [STOC 2004]. As a by-product, we improve upon the algorithm of Charalampopoulos et al. [CPM 2018] for computing a \( k \) -mismatch LCS in the case when the output \( k \) -mismatch LCS is sufficiently long.

Enumerating or counting combinatorial objects in graphs is a fundamental data mining task. We consider the problem of assessing the number of Eulerian trails in directed graphs, which is formalized as follows: Given a directed graph \(G=(V,E)\) , with \(|V|=n\) nodes and \(|E|=m\) edges, and an integer \( z \) , assess whether the number \(\#ET(G)\) of Eulerian trails of \( G \) is at least \( z \) . This problem underlies many applications in domains ranging from data privacy to computational biology, data compression, and transportation networks. Practitioners currently address this problem by applying the famous BEST theorem, which, in fact, counts \(\#ET(G)\) instead of just assessing whether \(\#ET(G)\geq z\) . Unfortunately, this solution takes \(\mathcal{O}(n^{\omega})\) arithmetic operations, where \(\omega < 2.373\) denotes the matrix multiplication exponent . Since in most real-world graphs, the number \( m \) of edges is comparable to the number \( n \) of nodes, and \( z \) is moderate in practice, the algorithmic challenge is: Can we solve the problem faster for certain values of \( m \) and \( z \) ? We want to design a combinatorial algorithm for assessing whether \(\#ET(G)\geq z\) , which does not resort to the BEST theorem and has a predictably bounded cost as a function of \( m \) and \( z \) . We address this challenge as follows. We first introduce a general algorithmic scheme for assessing (and enumerating) Eulerian trails. We then introduce a novel tree data structure to reduce the number of iterations in this general scheme. Finally, we complement the above with further combinatorial insight leading to an algorithm with a worst-case bound of \(\mathcal{O}(m\cdot\min\{z,\#ET(G)\})\) time. Our experiments using six benchmark datasets with multi-million edges from different domains show that our implementations are up to two orders of magnitude faster than the BEST theorem, perform much fewer than \(mz\) iterations and scale near-linearly with \( m \) in most cases. Our experiments further show that our implementations bring substantial efficiency benefits in a data privacy application which employs the BEST theorem for the assessment.

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word $C$ is an s-cover of a word $S$ if the occurrences of $C$ in $S$ as subsequences cover all the positions in $S$. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al., Inf. Process. Lett. 1991), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler, J. Comput. Syst. Sci. 1984). We give a linear-time algorithm for testing if a candidate word $C$ is an s-cover of a word $S$ over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word $S$, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].