3 Search Results for "Hait, Soumita"

Document
DOI: 10.4230/LIPIcs.ESA.2025.29
The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration

Authors: Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A dominating set of a graph G = (V,E) is a set of vertices D ⊆ V whose closed neighborhood is V, i.e., N[D] = V. We view a dominating set as a collection of tokens placed on the vertices of D. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in G by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth w, for some non-explicit constant w and to be XL-complete parameterized by the size k of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by k plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest. We complement these hardness results with a positive result showing that DSR (parameterized by k) in the sliding model is FPT on planar graphs, also answering an open problem from the literature.
Cite as

Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron. The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2025.29,
  author =	{Bousquet, Nicolas and Deschamps, Quentin and Mary, Arnaud and Mouawad, Amer E. and Pierron, Th\'{e}o},
  title =	{{The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.29},
  URN =		{urn:nbn:de:0030-drops-244974},
  doi =		{10.4230/LIPIcs.ESA.2025.29},
  annote =	{Keywords: combinatorial reconfiguration, parameterized complexity, structural graph parameters, treewidth, dominating set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.25
Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets

Authors: Anubhav Dhar, Soumita Hait, and Sudeshna Kolay

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The Euclidean Steiner Minimal Tree problem takes as input a set P of points in the Euclidean plane and finds the minimum length network interconnecting all the points of P. In this paper, in continuation to the works of [Du et al., 1987] and [Weng and Booth, 1995], we study Euclidean Steiner Minimal Tree when P is formed by the vertices of a pair of regular, concentric and parallel n-gons. We restrict our attention to the cases where the two polygons are not very close to each other. In such cases, we show that Euclidean Steiner Minimal Tree is polynomial-time solvable, and we describe an explicit structure of a Euclidean Steiner minimal tree for P. We also consider point sets P of size n where the number of input points not on the convex hull of P is f(n) ≤ n. We give an exact algorithm with running time 2^𝒪(f(n) log n) for such input point sets P. Note that when f(n) = 𝒪(n/(log n)), our algorithm runs in single-exponential time, and when f(n) = o(n) the running time is 2^o(n log n) which is better than the known algorithm in [Hwang et al., 1992]. We know that no FPTAS exists for Euclidean Steiner Minimal Tree unless P = NP [Garey et al., 1977]. On the other hand FPTASes exist for Euclidean Steiner Minimal Tree on convex point sets [Scott Provan, 1988]. In this paper, we show that if the number of input points in P not belonging to the convex hull of P is 𝒪(log n), then an FPTAS exists for Euclidean Steiner Minimal Tree. In contrast, we show that for any ε ∈ (0,1], when there are Ω(n^ε) points not belonging to the convex hull of the input set, then no FPTAS can exist for Euclidean Steiner Minimal Tree unless P = NP.
Cite as

Anubhav Dhar, Soumita Hait, and Sudeshna Kolay. Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dhar_et_al:LIPIcs.ISAAC.2023.25,
  author =	{Dhar, Anubhav and Hait, Soumita and Kolay, Sudeshna},
  title =	{{Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.25},
  URN =		{urn:nbn:de:0030-drops-193273},
  doi =		{10.4230/LIPIcs.ISAAC.2023.25},
  annote =	{Keywords: Steiner minimal tree, Euclidean Geometry, Almost Convex point sets, FPTAS, strong NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.39
On Finding Short Reconfiguration Sequences Between Independent Sets

Authors: Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer 𝓁 ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_𝓁 ⟩ of independent sets such that for all j ∈ {0,…,𝓁-1} the set I_j is an independent set of size k, I₀ = S, I_𝓁 = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most 𝓁 steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixed-parameter tractable when parameterized by 𝓁 on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixed-parameter tractable for parameter k + 𝓁 + d on d-degenerate graphs as well as for parameter |M| + 𝓁 + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter 𝓁 alone both problems become W[1]-hard already on 2-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.
Cite as

Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On Finding Short Reconfiguration Sequences Between Independent Sets. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
  author =	{Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
  title =	{{On Finding Short Reconfiguration Sequences Between Independent Sets}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.39},
  URN =		{urn:nbn:de:0030-drops-173244},
  doi =		{10.4230/LIPIcs.ISAAC.2022.39},
  annote =	{Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2022

  • Refine by Author
  • 2 Hait, Soumita
  • 2 Mouawad, Amer E.
  • 1 Agrawal, Akanksha
  • 1 Bousquet, Nicolas
  • 1 Deschamps, Quentin
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Finite Model Theory

  • Refine by Keyword
  • 2 combinatorial reconfiguration
  • 1 Almost Convex point sets
  • 1 Euclidean Geometry
  • 1 FPTAS
  • 1 Steiner minimal tree
  • Show More...

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
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact