Search Results

Documents authored by Mohanapriya, A


Document
Eccentricity Shortest Path Is W[1]-Hard Parameterized by Distance to Spider Graphs

Authors: Sriram Bhyravarapu and A Mohanapriya

Published in: LIPIcs, Volume 398, 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)


Abstract
In this work, we extend the study of the problem Eccentricity Shortest Path (ESP). In this problem, we are given as input a graph G and an integer q, and the goal is to check whether there exists a shortest path P such that every vertex u ∈ V(G) is within a distance at most q from some vertex of P. The problem arises naturally in transportation, logistics, and communication networks, which are often structured around a small set of primary routes. These routes must be both highly efficient and easily reachable from all parts of the network. Dragan and Leitert (TCS 2017) showed that Eccentricity Shortest Path is W[2]-hard when parameterized by q, and Bhyravarapu et al. (IWOCA 2023) demonstrated fixed-parameter tractability when parameterized by the combined parameters feedback vertex set number and q. Both works left open whether tractable algorithms exist when parameterized by the feedback vertex set number alone. We answer this question in negative by showing that Eccentricity Shortest Path is W[1]-hard when parameterized by distance to spider graphs. Since this parameter is a restricted case of feedback vertex set number and path-width, our result implies that Eccentricity Shortest Path remains W[1]-hard under these widely studied structural parameters. On the positive side, we consider the parameter feedback edge set number and present an algorithm running in time 2^𝒪(t log t) n^𝒪(1), where t denotes the feedback edge set number of the input graph with n vertices. Together, these results establish a clear dichotomy between intractability for vertex-deletion based structural parameters and fixed-parameter tractability for the more restrictive vertex/edge-deletion based parameters.

Cite as

Sriram Bhyravarapu and A Mohanapriya. Eccentricity Shortest Path Is W[1]-Hard Parameterized by Distance to Spider Graphs. In 21st International Symposium on Parameterized and Exact Computation (IPEC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 398, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.IPEC.2026.16,
  author =	{Bhyravarapu, Sriram and Mohanapriya, A},
  title =	{{Eccentricity Shortest Path Is W\lbrack1\rbrack-Hard Parameterized by Distance to Spider Graphs}},
  booktitle =	{21st International Symposium on Parameterized and Exact Computation (IPEC 2026)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-456-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{398},
  editor =	{Korhonen, Tuukka and Lampis, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2026.16},
  URN =		{urn:nbn:de:0030-drops-281896},
  doi =		{10.4230/LIPIcs.IPEC.2026.16},
  annote =	{Keywords: shortest path, W\lbrack1\rbrack-hard, feedback vertex set, path-width, clique-width, spider graphs, feedback edge set}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail