We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in O(ε^{-6}) semi-streaming passes, improving upon the O(ε^{-19}) pass-complexity algorithm by [Fischer, Mitrović, and Uitto, STOC'22]. This contributes substantially toward resolving Open question 2 from [Assadi, SOSA'24]. Leveraging the framework introduced in [FMU'22], our algorithm achieves an analogous round complexity speed-up for computing a (1+ε)-approximate maximum matching in both the Massively Parallel Computation (MPC) and CONGEST models. The data structures maintained by our algorithm are formulated using blossom notation and represented through alternating trees. This approach enables a simplified correctness analysis by treating specific components as if operating on bipartite graphs, effectively circumventing certain technical intricacies present in prior work.

We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of b-matching in which the input is a bipartite graph with capacities greater than 1 in only one part of the bipartition. We give a (1 + ϵ) approximate algorithm for the problem, which runs in Õ (√long λ) MPC rounds, using sublinear space per machine and Õ (λn) total space, where λ is the arboricity of the input graph. Our result is obtained by providing a new analysis of a LOCAL algorithm by Agrawal, Zadimoghaddam, and Mirrokni [ICML 2018], which improves its round complexity from O (log n) to O (log λ). Prior to our work, no o (log n) round algorithm for constant-approximate allocation was known in either LOCAL or sublinear space MPC models for graphs with low arboricity.

This work designs a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter ϵ > 0 and an oracle access to a Θ(1)-approximate maximum matching algorithm Ā. Then, by invoking Ā for poly(1/ϵ) many times, the framework outputs a 1 + ϵ approximation of a maximum matching. Our approach yields several improvements in terms of the number of invocations to Ā:

The split-row problem (SR), introduced by Hajirasouliha and Raphael [WABI 2014], models an effective method for reconstructing a perfect phylogeny from mixed tumor samples. In this problem, an $m \times n$ binary matrix $M$ is given. A split-row operation on $M$ is defined as replacing a row $r$ by $k > 1$ rows whose bitwise OR is equal to $r$. The cost of the operation is the number of additional rows induced, that is, $k - 1$. The objective is to find a sequence of operations that transforms $M$ into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Hujdurović et al. [TCBB 2018] proved the NP-hardness of SR. Let ${\rm{\varepsilon }}( M )$ denote the minimum total cost. In this paper, we show that SR admits a polynomial size kernel, which has at most $3{\rm{\varepsilon }}( M )$ rows and $4{\rm{\varepsilon }}( M ) - 1$ columns. Our kernelization algorithm requires $O( {\max ( {{{m}^{0.373}}{{n}^2}, m{{n}^{1.373}}} )} )$ time. When $\varepsilon ( M )$ is small, it can be used as a preprocessing procedure to speed up all previous exact algorithms for SR.

Consensus trees have been widely used in evolutionary studies to combine phylogenetic information of individual gene trees. This paper studies one of the most well-known consensus tree methods: the frequency difference consensus tree. Jansson et al. [IEEE/ACM TCBB, 2018] had an $O( {\text{min}}\{ {{{k}^2}n,\ k{{n}^2}} \} + kn\ \mathrm{l}{{\mathrm{g}}^2}n )$-time algorithm for constructing the frequency difference consensus tree of k phylogenetic trees on the same set of n taxa. Later, Gawrychowski et al. [ICALP, 2018] gave an improved upper bound of $O( {kn\ \mathrm{l}{{\mathrm{g}}^2}\ n} )$. This paper further reduces the upper bound to O(kn lg n). In addition, this paper presents a simple $O( {{{k}^2}n} )$-time algorithm. It is the fastest when k = O(lg n). Especially, when k = O(1), linear time is achieved.

Abstract. Motivated by an application in cancer genomics, Hajirasouliha and Raphael [ Proceedings of the 14 th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354–367] proposed the split-row problem (SR). In this problem, an [Formula: see text] binary matrix [Formula: see text] is given. A split-row operation on [Formula: see text] is defined as replacing a row [Formula: see text] by [Formula: see text] rows [Formula: see text] whose bitwise OR is equal to [Formula: see text]. The cost of the operation is the number of additional rows induced, that is, [Formula: see text]. The goal is to find a sequence of split-row operations that transforms [Formula: see text] into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurović et al. [ ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let [Formula: see text] denote the minimum total cost. This paper gives an [Formula: see text]-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by [Formula: see text]. In addition, in the worst case, our algorithm requires [Formula: see text] time, significantly improving the previous upper bound of [Formula: see text]. Hujdurović et al.’s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split.