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.(c) 2023 Elsevier B.V. All rights reserved.

Bekos, M.a., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.n. (2023). Recognizing DAGs with page-number 2 is NP-complete. THEORETICAL COMPUTER SCIENCE, 946, 113689 [10.1016/j.tcs.2023.113689].

Recognizing DAGs with page-number 2 is NP-complete

Da Lozzo, G
;
Frati, F
;
2023-01-01

Abstract

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.(c) 2023 Elsevier B.V. All rights reserved.
2023
Bekos, M.a., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.n. (2023). Recognizing DAGs with page-number 2 is NP-complete. THEORETICAL COMPUTER SCIENCE, 946, 113689 [10.1016/j.tcs.2023.113689].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/433547
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact