2026-08-21T18:34:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27455 2026-08-21T14:42:40Z ddc:004 open_access

Parameterizing the Complexity of Finding Long Paths in DAGs Bhadra, Ronak Singh, Saurya Tewari, Raghunath Unambiguous Computations Directed Acyclic Graphs Space Complexity Given a graph G and two vertices s and t, the Long Path problem asks whether there exists a path of length at least k from s to t. For general graphs, this problem is NP-hard when k is part of the input. For directed acyclic graphs (DAGs), however, it is solvable in polynomial time and is NL-complete. A nondeterministic logspace computation is said to be unambiguous if, on every input, there is at most one accepting computation path. The class UL consists of all problems solvable by such machines, and whether NL = UL is an open question. In this work, we study the unambiguous complexity of the Long Path problem on DAGs under parameterization. Specifically, we consider the problem of deciding whether there exists a path of length at least n-k between two given vertices in a DAG. Bhadra and Tewari [Ronak Bhadra and Raghunath Tewari, 2025] showed that this problem can be solved in unambiguous and co-unambiguous O(klog n) space. We improve this result by giving an algorithm that runs in unambiguous O(k+log n) space. Additionally, we obtain an algorithm that achieves unambiguous and co-unambiguous O(klog n) space while running in time polynomial in both n and k, improving the previous O^*(n^k) time bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ronak Bhadra and Saurya Singh and Raghunath Tewari 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.73 urn:nbn:de:0030-drops-274557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.73 eng https://creativecommons.org/licenses/by/4.0/legalcode