Search Results

Documents authored by Kirkpatrick, Yael

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.50
New Additive Approximations for Shortest Paths and Cycles

Authors: Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong

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

Abstract
This paper considers additive approximation algorithms for All-Pairs Shortest Paths (APSP) and Shortest Cycle in undirected unweighted graphs. The results are as follows: - We obtain the first +2-approximation algorithm for APSP in n-vertex graphs that improves upon Dor, Halperin and Zwick’s (SICOMP'00) Õ(n^{7/3}) time algorithm. The new algorithm runs in Õ(n^2.29) time and is obtained via a reduction to Min-Plus product of bounded difference matrices. - We obtain the first additive approximation scheme for Shortest Cycle, generalizing the approximation algorithms of Itai and Rodeh (SICOMP'78) and Roditty and Vassilevska W. (SODA'12). For every integer r ≥ 0, we give an Õ(n+n^{2+r}/m^r) time algorithm that returns a +(2r+1)-approximate shortest cycle in any n-vertex, m-edge graph.
Cite as

Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong. New Additive Approximations for Shortest Paths and Cycles. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.ICALP.2022.50,
  author =	{Deng, Mingyang and Kirkpatrick, Yael and Rong, Victor and Vassilevska Williams, Virginia and Zhong, Ziqian},
  title =	{{New Additive Approximations for Shortest Paths and Cycles}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{50:1--50:10},
  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.50},
  URN =		{urn:nbn:de:0030-drops-163919},
  doi =		{10.4230/LIPIcs.ICALP.2022.50},
  annote =	{Keywords: Fine-grained Complexity, Additive Approximation}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact