20.500.12556/RUL-176951 Testing whether a subgraph is convex or isometric 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$. convex subgraphs isometric subgraphs plane graphs true false true Angleški jezik Angleški jezik Članek v reviji 2025-12-16 12:35:42 2025-12-16 12:35:44 2025-12-17 04:40:05 0000-00-00 00:00:00 2025 0 0 Str. 12:1-12:16 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42:519.17 10.4230/LIPIcs.WADS.2025.12 261640963 261608451 LIPIcs.WADS.2025.12.pdf LIPIcs.WADS.2025.12.pdf 1 E2493B11AEAA6D83727FBE9FC2B42137 d0fc4b75597c46cf4b9c1fdccfe220b3252a4dec4ac3a11ee18c6b40951b8d4f ba5d6abf-da73-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=223791 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.12 1 ec4904aa-da72-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=223790 Fakulteta za matematiko in fiziko 0 0 0