Search Results

Documents authored by Lahiri, Abhiruk

Document
DOI: 10.4230/LIPIcs.IPEC.2024.23
Parameterized Shortest Path Reconfiguration

Authors: Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, and Amer E. Mouawad

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A reconfiguration sequence between two st-paths P and Q is a sequence of adjacent st-paths starting from P and ending at Q. Deciding whether there exists a reconfiguration sequence between two given st-paths is known to be PSPACE-complete, even on restricted classes of graphs such as graphs of bounded bandwidth (hence pathwidth). On the positive side, and rather surprisingly, the problem is polynomial-time solvable on planar graphs. In this paper, we study the parameterized complexity of the Shortest Path Reconfiguration (SPR) problem. We show that SPR is W[1]-hard parameterized by k + 𝓁, even when restricted to graphs of bounded (constant) degeneracy; here k denotes the number of edges on an st-path, and 𝓁 denotes the length of a reconfiguration sequence from P to Q. We complement our hardness result by establishing the fixed-parameter tractability of SPR parameterized by 𝓁 and restricted to nowhere-dense classes of graphs. Additionally, we establish fixed-parameter tractability of SPR when parameterized by the treedepth, by the cluster-deletion number, or by the modular-width of the input graph.
Cite as

Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, and Amer E. Mouawad. Parameterized Shortest Path Reconfiguration. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.IPEC.2024.23,
  author =	{Bousquet, Nicolas and Gajjar, Kshitij and Lahiri, Abhiruk and Mouawad, Amer E.},
  title =	{{Parameterized Shortest Path Reconfiguration}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.23},
  URN =		{urn:nbn:de:0030-drops-222491},
  doi =		{10.4230/LIPIcs.IPEC.2024.23},
  annote =	{Keywords: combinatorial reconfiguration, shortest path reconfiguration, parameterized complexity, structural parameters, treedepth, cluster deletion number, modular width}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.38
On Comparable Box Dimension

Authors: Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.
Cite as

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten},
  title =	{{On Comparable Box Dimension}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38},
  URN =		{urn:nbn:de:0030-drops-160461},
  doi =		{10.4230/LIPIcs.SoCG.2022.38},
  annote =	{Keywords: geometric graphs, minor-closed graph classes, treewidth fragility}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.40
Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs

Authors: Zdeněk Dvořák and Abhiruk Lahiri

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable on graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property which is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
Cite as

Zdeněk Dvořák and Abhiruk Lahiri. Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 40:1-40:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.40,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Lahiri, Abhiruk},
  title =	{{Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{40:1--40:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.40},
  URN =		{urn:nbn:de:0030-drops-146216},
  doi =		{10.4230/LIPIcs.ESA.2021.40},
  annote =	{Keywords: approximation, sublinear separators}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact