论文标题
参数化线性时间的最小路径覆盖
Minimum Path Cover in Parameterized Linear Time
论文作者
论文摘要
有向无环图（DAG）的最小路径盖（MPC）$ g =（v，e）$是一组最小尺寸的路径，覆盖了DAG的所有顶点。计算MPC是一个基本的多项式问题，可以追溯到Dilworth's和Fulkerson在1950年代的结果。由于MPC（也称为宽度）的尺寸$ K $在实际应用中可能很小，因此研究还研究了其运行时间在$ k $上进行参数化的算法。 我们获得了一种新的MPC参数化算法，用于在时间$ O（k^2 | v | + | e |）$中运行的DAG。我们的算法是第一个在参数化线性时间中解决问题的问题。此外，我们获得了一种边缘稀疏算法，该算法保留了DAG的宽度，但将$ | e | $减少到$ 2 | v | $。该算法在时间$ o（k^2 | v |）$中运行，并且需要一个DAG作为输入的MPC，因此其总运行时间与我们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 running time is parameterized on $k$. We obtain a new MPC parameterized algorithm for DAGs running in time $O(k^2|V| + |E|)$. Our algorithm is the first solving the problem in parameterized linear time. Additionally, we obtain an edge sparsification algorithm preserving the width of a DAG but reducing $|E|$ to less than $2|V|$. This algorithm runs in time $O(k^2|V|)$ and requires an MPC of a DAG as input, thus its total running time is the same as the running time of our MPC algorithm.
