Testing whether a subgraph is convex or isometric

Cabello, Sergio (author)

We consider the following two algorithmic problems: given a graph $G$ and a subgraph $H\subseteq G$, decide whether $H$ is an isometric or a geodesically convex subgraph of $G$. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with $n$ vertices and $\Theta(n)$ edges, we cannot expect to solve the problem in $O(n^{2-\varepsilon})$ time for any constant $\varepsilon>0$. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where $G$ is a plane graph and $H$ is defined by a few cycles in $G$.

• Language: English
• Keywords: convex subgraphs, isometric subgraphs, plane graphs
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: Str. 12:1-12:16
• PID: 20.500.12556/RUL-176951
• UDC: 004.42:519.17
• DOI: 10.4230/LIPIcs.WADS.2025.12
• COBISS.SI-ID: 261640963
• Publication date in RUL: 16.12.2025

Record is a part of a monograph

• Title: 19th International Symposium on Algorithms and Data Structures : WADS 2025, August 11–15, 2025, York University, Toronto, Canada
• Editors: Pat Morin, Eunjin Oh
• Place of publishing: Saarbrücken/Wadern
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Year: 2025
• ISBN: 978-3-95977-398-0
• COBISS.SI-ID: 261608451
• Collection title: Leibniz international proceedings in informatics
• Collection numbering: ǂvol. ǂ349
• Collection ISSN: 1868-8969

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.