Complexity of some Path Problems in DAGs and Linear Orders
arXiv:0710.2268
Abstract
We investigate here the computational complexity of three natural problems in directed acyclic graphs. We prove their NP Completeness and consider their restrictions to linear orders.
5 pages, 3 figures