On The Complexity of the Shortest Path Problem in a Layered Directed Acyclic Graph with Consistency Constraints

Dubray, Alexandre;Derval, Guillaume;Nijssen, Siegfried;Schaus, Pierre
(2022)

Files

np-hardness-proof.pdf
  • Open Access
  • Adobe PDF
  • 376.46 KB
Download

Details

Authors
Abstract
In this document, we explore the complexity of the shortest path problem in a layered directed acyclic graph under consistency constraints. In this context, a consistency constraint imposes that the optimal path select nodes with the same labels in some layers of the graph. We show that this problem is NP-Hard by reducing the 3-SAT problem to it.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Dubray, A., Derval, G., Nijssen, S., & Schaus, P. (2022). On The Complexity of the Shortest Path Problem in a Layered Directed Acyclic Graph with Consistency Constraints. https://hdl.handle.net/2078.5/273352