DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.73

Parameterizing the Complexity of Finding Long Paths in DAGs

Authors: Ronak Bhadra, Saurya Singh, and Raghunath Tewari

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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.

Cite as

Ronak Bhadra, Saurya Singh, and Raghunath Tewari. Parameterizing the Complexity of Finding Long Paths in DAGs. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhadra_et_al:LIPIcs.MFCS.2026.73,
  author =	{Bhadra, Ronak and Singh, Saurya and Tewari, Raghunath},
  title =	{{Parameterizing the Complexity of Finding Long Paths in DAGs}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.73},
  URN =		{urn:nbn:de:0030-drops-274557},
  doi =		{10.4230/LIPIcs.MFCS.2026.73},
  annote =	{Keywords: Unambiguous Computations, Directed Acyclic Graphs, Space Complexity}
}

Search Results

Documents authored by Singh, Saurya

Parameterizing the Complexity of Finding Long Paths in DAGs

Abstract

Cite as

Thanks for your feedback!

Could not send message