论文标题
使用页面数2识别DAG是NP完整的
Recognizing DAGs with Page-Number 2 is NP-complete
论文作者
论文摘要
定向无环图的页面数（简称为DAG）是DAG的最低$ k $，其边缘的拓扑顺序和$ k $ - 颜色的边缘颜色，因此没有两个相同的颜色交叉的边缘，即沿拓扑顺序具有交替的端点。 1999年，希思（Heath）和彭玛拉朱（Pemmaraju）猜想，识别page-number $ 2 $的达格（DAG）是np-complete，并证明识别page-number $ 6 $的dag是np-complete [siam J. Computing，1999]。 Binucci等。最近，通过证明使用page-number $ k $的dags的dag是np-complete，每$ k \ geq 3 $ [SOCG 2019]，从而增强了这一结果。在本文中，我们终于在肯定中解决了希思和彭马拉朱的猜想。特别是，我们的NP完整结果即使在$ ST $ - 平面图和平面posets中也可以。
The page-number of a directed acyclic graph (a DAG, for short) is the minimum $k$ for which the DAG has a topological order and a $k$-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number $2$ is NP-complete and proved that recognizing DAGs with page-number $6$ is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for $st$-planar graphs and planar posets.
