Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
复制标题
DOI：
10.1137/1.9781611977073.18
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Manuel O. C'aceres;Massimo Cairo;B. Mumey;Romeo Rizzi;Alexandru I. Tomescu
中科院分区：
文献类型：
--
作者：
Manuel O. C'aceres;Massimo Cairo;B. Mumey;Romeo Rizzi;Alexandru I. Tomescu
有向无环图（DAG）$G =（V，E）$的最小路径覆盖（MPC）是覆盖DAG所有顶点的最小路径集。计算MPC是一个基本的多项式问题，可以追溯到20世纪50年代Dilworth和Fulkerson的结果。由于MPC的大小$k$（也称为宽度）在实际应用中可能很小，因此研究人员还研究了其复杂度以$k$为参数的算法。我们得到了两个新的MPC参数化算法，时间复杂度为$O（k^2| V|登录|V|} + |E|时间复杂度O（k ^3）|V| + |E|)$.我们还得到了一个时间复杂度为$O（k^2）的并行算法|V| + |E|）$ parallel steps和使用$O（\log{|V|}）$ processors（在PRAM模型中）。后两个算法是首次在参数化线性时间内求解该问题。最后，我们给出了一个时间复杂度为$O（k^2）的算法|V|）$用于将任何MPC转换为另一个MPC，使用不到2美元|V| $不同的边缘，我们证明是渐近紧。因此，我们还获得了边缘稀疏化算法，保留了DAG的宽度，运行时间与我们的MPC算法相同。在我们所有的算法的核心，我们交错使用三种技术：传递稀疏化，收缩的路径覆盖，和拼接的一组路径沿着一个给定的路径。
A minimum path cover (MPC) of a directed acyclic graph (DAG) $G = (V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size $k$ of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose complexity is parameterized on $k$. We obtain two new MPC parameterized algorithms for DAGs running in time $O(k^2|V|\log{|V|} + |E|)$ and $O(k^3|V| + |E|)$. We also obtain a parallel algorithm running in $O(k^2|V| + |E|)$ parallel steps and using $O(\log{|V|})$ processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we present an algorithm running in time $O(k^2|V|)$ for transforming any MPC to another MPC using less than $2|V|$ distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.