Recognizing DAGs with page-number 2 is NP-complete

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 conjectur...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2023-02, Vol.946, p.113689, Article 113689
Main Authors: Bekos, Michael A., Da Lozzo, Giordano, Frati, Fabrizio, Gronemann, Martin, Mchedlidze, Tamara, Raftopoulou, Chrysanthi N.
Format: Article
Language:English
Subjects:
Directed acyclic graphs
Page-number
Planar posets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (Heath and Pemmaraju (1999) [15]). Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k≥3 (Binucci et al. (2019) [6]). 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.
ISSN:0304-3975
DOI:10.1016/j.tcs.2023.113689