Search Results

Documents authored by Rathod, Abhishek

Document
DOI: 10.4230/LIPIcs.SoCG.2026.5
Bifunction and Interlevel Delaunay Trifiltrations

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an ℝ-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an ℝ²-valued function, also satisfying an analogous weak equivalence. For a point cloud X ⊂ ℝ^d, our trifiltration has size O(|X|^{⌈(d+1)/2⌉+1}). We present an algorithm that computes this trifiltration in time O(|X|^{⌈d/2⌉+2}), together with an implementation. Our experiments demonstrate that the implementation can handle thousands of points in ℝ³, with memory growth that is nearly linear.
Cite as

Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod. Bifunction and Interlevel Delaunay Trifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:LIPIcs.SoCG.2026.5,
  author =	{Alonso, \'{A}ngel Javier and Kerber, Michael and Lam, Tung and Lesnick, Michael and Rathod, Abhishek},
  title =	{{Bifunction and Interlevel Delaunay Trifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.5},
  URN =		{urn:nbn:de:0030-drops-258118},
  doi =		{10.4230/LIPIcs.SoCG.2026.5},
  annote =	{Keywords: Delaunay triangulation, Multiparameter persistent homology, Interlevel, Bowyer-Watson}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.82
(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs

Authors: Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, T-Cycle: given an undirected n-vertex graph G and a set of k vertices T ⊆ V(G) termed terminals, the objective is to determine whether G contains a simple cycle C through all the terminals. Our contribution is twofold: (i) We provide a 2^{O(√klog k)}⋅ n-time fixed-parameter deterministic algorithm for T-Cycle on planar graphs; (ii) We provide a k^{O(1)}⋅ n-time deterministic kernelization algorithm for T-Cycle on planar graphs where the produced instance is of size klog^{O(1)}k. Both of our algorithms are optimal in terms of both k and n up to (poly)logarithmic factors in k under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for T-Cycle on planar graphs, as well as the first polynomial kernel for T-Cycle on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.
Cite as

Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi. (Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.ICALP.2025.82,
  author =	{Gahlawat, Harmender and Rathod, Abhishek and Zehavi, Meirav},
  title =	{{(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{82:1--82:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.82},
  URN =		{urn:nbn:de:0030-drops-234593},
  doi =		{10.4230/LIPIcs.ICALP.2025.82},
  annote =	{Keywords: FPT Algorithms, Kernelization, T-Cycle, Subexponential Algorithmms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.50
Cup Product Persistence and Its Efficient Computation

Authors: Tamal K. Dey and Abhishek Rathod

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
It is well-known that the cohomology ring has a richer structure than homology groups. However, until recently, the use of cohomology in persistence setting has been limited to speeding up of barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an O(d n⁴) algorithm for computing the persistent k-cup modules for all k ∈ {2, … , d}, where d denotes the dimension of the filtered complex, and n denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it for d ≥ 3. Finally, we introduce a new stable invariant called partition modules of cup product that is more discriminative than persistent cup modules and devise an O(c(d)n⁴) algorithm for computing it, where c(d) is subexponential in d.
Cite as

Tamal K. Dey and Abhishek Rathod. Cup Product Persistence and Its Efficient Computation. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.50,
  author =	{Dey, Tamal K. and Rathod, Abhishek},
  title =	{{Cup Product Persistence and Its Efficient Computation}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.50},
  URN =		{urn:nbn:de:0030-drops-199958},
  doi =		{10.4230/LIPIcs.SoCG.2024.50},
  annote =	{Keywords: Persistent cohomology, cup product, image persistence, persistent cup module}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.13
On Computing Homological Hitting Sets

Authors: Ulrich Bauer, Abhishek Rathod, and Meirav Zehavi

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Cut problems form one of the most fundamental classes of problems in algorithmic graph theory. In this paper, we initiate the algorithmic study of a high-dimensional cut problem. The problem we study, namely, Homological Hitting Set (HHS), is defined as follows: Given a nontrivial r-cycle z in a simplicial complex, find a set 𝒮 of r-dimensional simplices of minimum cardinality so that 𝒮 meets every cycle homologous to z. Our first result is that HHS admits a polynomial-time solution on triangulations of closed surfaces. Interestingly, the minimal solution is given in terms of the cocycles of the surface. Next, we provide an example of a 2-complex for which the (unique) minimal hitting set is not a cocycle. Furthermore, for general complexes, we show that HHS is W[1]-hard with respect to the solution size p. In contrast, on the positive side, we show that HHS admits an FPT algorithm with respect to p+Δ, where Δ is the maximum degree of the Hasse graph of the complex 𝖪.
Cite as

Ulrich Bauer, Abhishek Rathod, and Meirav Zehavi. On Computing Homological Hitting Sets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.ITCS.2023.13,
  author =	{Bauer, Ulrich and Rathod, Abhishek and Zehavi, Meirav},
  title =	{{On Computing Homological Hitting Sets}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.13},
  URN =		{urn:nbn:de:0030-drops-175169},
  doi =		{10.4230/LIPIcs.ITCS.2023.13},
  annote =	{Keywords: Algorithmic topology, Cut problems, Surfaces, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.64
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis

Authors: Abhishek Rathod

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with ℤ₂ coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. [Dey et al., 2018], runs in O(N^ω + N² g) time, where N denotes the number of simplices in K, g denotes the rank of the 1-homology group of K, and ω denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K. The first algorithm runs in Õ(m^ω) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^ω + N m^{ω-1}) time. We also study the problem of finding a minimum cycle basis in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O(m^ω) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in Õ(m^ω) time.
Cite as

Abhishek Rathod. Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 64:1-64:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rathod:LIPIcs.SoCG.2020.64,
  author =	{Rathod, Abhishek},
  title =	{{Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{64:1--64:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.64},
  URN =		{urn:nbn:de:0030-drops-122223},
  doi =		{10.4230/LIPIcs.SoCG.2020.64},
  annote =	{Keywords: Computational topology, Minimum homology basis, Minimum cycle basis, Simplicial complexes, Matrix computations}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.13
Parametrized Complexity of Expansion Height

Authors: Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is famously undecidable. There exists a combinatorial refinement of this concept, called simple-homotopy equivalence: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion. In this article we consider the following related problem: given a 2-dimensional simplicial complex, is there a simple-homotopy equivalence to a 1-dimensional simplicial complex using at most p expansions? We show that the problem, which we call the erasability expansion height, is W[P]-complete in the natural parameter p.
Cite as

Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer. Parametrized Complexity of Expansion Height. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.ESA.2019.13,
  author =	{Bauer, Ulrich and Rathod, Abhishek and Spreer, Jonathan},
  title =	{{Parametrized Complexity of Expansion Height}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.13},
  URN =		{urn:nbn:de:0030-drops-111346},
  doi =		{10.4230/LIPIcs.ESA.2019.13},
  annote =	{Keywords: Simple-homotopy theory, simple-homotopy type, parametrized complexity theory, simplicial complexes, (modified) dunce hat}
}
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