3 Search Results for "Mathialagan, Surya"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.63
Shortest Paths in Multimode Graphs

Authors: Yael Kirkpatrick and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimode shortest path is the shortest path using one of multiple "modes" of transportation that cannot be combined. This represents real-world scenarios where different modes are not combinable, such as flights operated by different airline alliances. The problem arises naturally in machine learning in the context of learning with multiple embedding. More precisely, a k-multimode graph is a collection of k graphs on the same vertex set and the k-mode distance between two vertices is defined as the minimum among the distances computed in each individual graph. We focus on approximating fundamental graph parameters on these graphs, specifically diameter and radius. In undirected multimode graphs we first show an elegant linear time 3-approximation algorithm for 2-mode diameter. We then extend this idea into a general subroutine that can be used as a part of any α-approximation, and use it to construct a 2 and 2.5 approximation algorithm for 2-mode diameter. For undirected radius, we introduce a general scheme that can compute a 3-approximation of the k-mode radius for any k and runs in near linear time in the case of k = O(1). In the directed case we establish an equivalence between approximating 2-mode diameter on DAGs and approximating the min-diameter, while for general graphs we develop novel techniques and provide a linear time algorithm to determine whether the diameter is finite. We also develop many conditional fine-grained lower bounds for various multimode diameter and radius approximation problems. We are able to show that many of our algorithms are tight under popular fine-grained complexity hypotheses, including our linear time 3-approximation for 3-mode undirected diameter and radius. As part of this effort we propose the first extension to the Hitting Set Hypothesis [SODA'16], which we call the 𝓁-Hitting Set Hypothesis. We use this hypothesis to prove the first parameterized lower bound tradeoff for radius approximation algorithms.
Cite as

Yael Kirkpatrick and Virginia Vassilevska Williams. Shortest Paths in Multimode Graphs. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kirkpatrick_et_al:LIPIcs.MFCS.2025.63,
  author =	{Kirkpatrick, Yael and Vassilevska Williams, Virginia},
  title =	{{Shortest Paths in Multimode Graphs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.63},
  URN =		{urn:nbn:de:0030-drops-241703},
  doi =		{10.4230/LIPIcs.MFCS.2025.63},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Diameter, Radius, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.38
Graph Threading

Authors: Erik D. Demaine, Yael Kirkpatrick, and Rebecca Lin

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired graph. More precisely, given a connected graph (where edges represent tubes and vertices represent junctions where they meet), we give a polynomial-time algorithm to find a minimum-length closed walk (representing a threading of string) that induces a connected graph of string at every junction. The algorithm is based on a surprising reduction to minimum-weight perfect matching. Along the way, we give tight worst-case bounds on the length of the optimal threading and on the maximum number of times this threading can visit a single edge. We also give more efficient solutions to two special cases: cubic graphs and the case when each edge can be visited at most twice.
Cite as

Erik D. Demaine, Yael Kirkpatrick, and Rebecca Lin. Graph Threading. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.ITCS.2024.38,
  author =	{Demaine, Erik D. and Kirkpatrick, Yael and Lin, Rebecca},
  title =	{{Graph Threading}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.38},
  URN =		{urn:nbn:de:0030-drops-195665},
  doi =		{10.4230/LIPIcs.ITCS.2024.38},
  annote =	{Keywords: Shortest walk, Eulerian cycle, perfect matching, beading}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.94
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Authors: Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The AP-LCA problem asks, given an n-node directed acyclic graph (DAG), to compute for every pair of vertices u and v in the DAG a lowest common ancestor (LCA) of u and v if one exists, i.e. a node that is an ancestor of both u and v but no proper descendent of it is their common ancestor. Recently [Grandoni et al. SODA'21] obtained the first sub-n^{2.5} time algorithm for AP-LCA running in O(n^{2.447}) time. Meanwhile, the only known conditional lower bound for AP-LCA is that the problem requires n^{ω-o(1)} time where ω is the matrix multiplication exponent. In this paper we study several interesting variants of AP-LCA, providing both algorithms and fine-grained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than n^{ω-o(1)}. Some of our results include: - In any DAG, we can detect all vertex pairs that have at most two LCAs and list all of their LCAs in O(n^ω) time. This algorithm extends a result of [Kowaluk and Lingas ESA'07] which showed an Õ(n^ω) time algorithm that detects all pairs with a unique LCA in a DAG and outputs their corresponding LCAs. - Listing 7 LCAs per vertex pair in DAGs requires n^{3-o(1)} time under the popular assumption that 3-uniform 5-hyperclique detection requires n^{5-o(1)} time. This is surprising since essentially cubic time is sufficient to list all LCAs (if ω = 2). - Counting the number of LCAs for every vertex pair in a DAG requires n^{3-o(1)} time under the Strong Exponential Time Hypothesis, and n^{ω(1,2,1)-o(1)} time under the 4-Clique hypothesis. This shows that the algorithm of [Echkardt, Mühling and Nowak ESA'07] for listing all LCAs for every pair of vertices is likely optimal. - Given a DAG and a vertex w_{u,v} for every vertex pair u,v, verifying whether all w_{u,v} are valid LCAs requires n^{2.5-o(1)} time assuming 3-uniform 4-hyperclique requires n^{4-o(1)} time. This defies the common intuition that verification is easier than computation since returning some LCA per vertex pair can be solved in O(n^{2.447}) time.
Cite as

Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 94:1-94:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mathialagan_et_al:LIPIcs.ICALP.2022.94,
  author =	{Mathialagan, Surya and Vassilevska Williams, Virginia and Xu, Yinzhan},
  title =	{{Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{94:1--94:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.94},
  URN =		{urn:nbn:de:0030-drops-164359},
  doi =		{10.4230/LIPIcs.ICALP.2022.94},
  annote =	{Keywords: All-Pairs Lowest Common Ancestor, Fine-Grained Complexity}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

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

  • Refine by Author
  • 2 Kirkpatrick, Yael
  • 2 Vassilevska Williams, Virginia
  • 1 Demaine, Erik D.
  • 1 Lin, Rebecca
  • 1 Mathialagan, Surya
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 2 Fine-Grained Complexity
  • 1 All-Pairs Lowest Common Ancestor
  • 1 Diameter
  • 1 Eulerian cycle
  • 1 Graph Algorithms
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact