Abstract Given an undirected graphGonnnodes andmedges in the form of a data stream we study the problem of finding an Euler tour inG. Our main result is the first one-pass streaming algorithm computing an Euler tour ofGin the form of an edge successor function with only $\mathcal O(n\log (n))$ O(nlog(n)) RAM, which is optimal for this setting (e.g. Sun and Woodruff (2015)). Since the output size can be much larger, we use a write-only tape to gradually output the solution. The previously best-known result for finding Euler tours in data streams is implicitly given by the W-stream algorithm of Demetrescu et al. (2010) using $\mathcal O(m/n)$ O(m/n) passes under the same RAM limitation. Our approach is to partition the edges into edge-disjoint cycles and to merge the cycles until a single Euler tour is achieved. In the streaming environment such a merging is far from being obvious as the limited RAM allows the processing of only a constant number of cycles at once. This enforces merging of cycles that partially are no longer present in RAM. We solve this problem with a new edge swapping technique, for which storing two certain edges per node is sufficient to merge tours without having all tour edges in RAM. The mathematical key is to model tours and their merging in an algebraic way, where certain equivalence classes represent subtours. This quite general approach might be of interest also in other routing problems.

BACKGROUND: For single-cell or metagenomic sequencing projects, it is necessary to sequence with a very high mean coverage in order to make sure that all parts of the sample DNA get covered by the reads produced. This leads to huge datasets with lots of redundant data. A filtering of this data prior to assembly is advisable. Brown et al. (2012) presented the algorithm Diginorm for this purpose, which filters reads based on the abundance of their k-mers. METHODS: We present Bignorm, a faster and quality-conscious read filtering algorithm. An important new algorithmic feature is the use of phred quality scores together with a detailed analysis of the k-mer counts to decide which reads to keep. RESULTS: We qualify and recommend parameters for our new read filtering algorithm. Guided by these parameters, we remove in terms of median 97.15% of the reads while keeping the mean phred score of the filtered dataset high. Using the SDAdes assembler, we produce assemblies of high quality from these filtered datasets in a fraction of the time needed for an assembly from the datasets filtered with Diginorm. CONCLUSIONS: We conclude that read filtering is a practical and efficient method for reducing read data and for speeding up the assembly process. This applies not only for single cell assembly, as shown in this paper, but also to other projects with high mean coverage datasets like metagenomic sequencing projects. Our Bignorm algorithm allows assemblies of competitive quality in comparison to Diginorm, while being much faster. Bignorm is available for download at https://git.informatik.uni-kiel.de/axw/Bignorm .

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.

Abstract We consider the problem of connecting a set 1 of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k ∈ IN. For k = Ω(logN + log2n) Oruç (J Parallet Distributed Comput 1994, 359–366 10 ) gave the presently best (n,N)‐connector with O(N + n · logn) edges. For k = 2 and N the square of a prime, Richards and Hwang (1985) described a construction using $N\lceil\sqrt{n + 5/4} - 1/2\rceil + n\lceil\sqrt{n + 5/4} - 1/2 \rceil \sqrt{N}$ edges. We show by a probabilistic argument that an optimal (n,N)‐connector has Θ(N) edges, if n ≤ N½−ε for some ∈ ≥ 0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most $N\lceil \sqrt{3n/4}\rceil + 2n\lceil \sqrt {3n/4}\rceil\lceil\sqrt{N}\rceil$ edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdős‐Heilbronn conjecture on the size of restricted sums. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 119–124 2005