论文标题
用于计算DAG宽度的线性时间参数化算法
A linear-time parameterized algorithm for computing the width of a DAG
论文作者
论文摘要
定向无环图的宽度$ k $（dag）$ g =（v，e）$等于最大的成对不可访问的顶点。计算宽度的历史可以追溯到1950年代Dilworth和Fulkerson的结果，在最坏情况下，在二次时期可行。由于$ k $在实际应用中可能很小，因此研究还研究了其复杂性在$ k $上进行参数化的算法。尽管有这些努力，但是否存在线性时间$ o（f（k）（| v | + | e |））$参数化算法计算宽度。我们通过提出$ o（K^24^k | + k2^k | e |）$ time Algorithm的肯定回答了这个问题。当我们按拓扑顺序处理顶点时，可以在几个组合属性的帮助下维护所有边界敌，一路上仅支付$ f（k）$。宽度可以通过单个$ f（k）$ - DAG扫描来计算的宽度是对这个经典问题的一个新的令人惊讶的见解。我们的算法还允许确定DAG是否具有最多宽度$ W $ in Time $ o（f（\ min（w，k））（| v |+| e |））$。
The width $k$ of a directed acyclic graph (DAG) $G = (V, E)$ equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth's and Fulkerson's results in the 1950s, and is doable in quadratic time in the worst case. Since $k$ can be small in practical applications, research has also studied algorithms whose complexity is parameterized on $k$. Despite these efforts, it is still open whether there exists a linear-time $O(f(k)(|V| + |E|))$ parameterized algorithm computing the width. We answer this question affirmatively by presenting an $O(k^24^k|V| + k2^k|E|)$ time algorithm, based on a new notion of frontier antichains. As we process the vertices in a topological order, all frontier antichains can be maintained with the help of several combinatorial properties, paying only $f(k)$ along the way. The fact that the width can be computed by a single $f(k)$-sweep of the DAG is a new surprising insight into this classical problem. Our algorithm also allows deciding whether the DAG has width at most $w$ in time $O(f(\min(w,k))(|V|+|E|))$.
