pith. sign in

arxiv: 2502.16193 · v3 · submitted 2025-02-22 · 💻 cs.DS

Testing whether a subgraph is convex or isometric

Sergio Cabello This is my paper

Pith reviewed 2026-05-23 02:42 UTC · model grok-4.3

classification 💻 cs.DS
keywords isometric subgraphgeodesically convex subgraphconditional lower boundplanar graphsbounded treewidthsubquadratic algorithms
0
0 comments X

The pith

Isometric and convex subgraph tests cannot run in subquadratic time on sparse graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the problems of deciding whether a given subgraph H inside a graph G preserves all distances from G or contains all shortest paths between its own vertices. These checks reduce to computing distances between every pair of vertices, yet the authors prove that no algorithm faster than quadratic time exists for graphs that have only a linear number of edges. They supply compensating positive results: subquadratic algorithms when G is planar, near-linear algorithms when G has bounded treewidth, and near-linear algorithms when G is a plane graph and H is delimited by a constant number of cycles. A reader cares because the negative result shows that two natural structural questions about subgraphs inherit the quadratic barrier that governs distance computation in sparse graphs.

Core claim

The problems of testing whether a subgraph is isometric or geodesically convex cannot be solved in subquadratic time when the host graph is sparse, as established by conditional lower bounds, although the same problems admit subquadratic solutions on planar graphs and near-linear solutions on graphs of bounded treewidth or on plane graphs whose subgraph is delimited by few cycles.

What carries the argument

Conditional lower bounds obtained by reduction from all-pairs distance computation, which establish that quadratic time is necessary for the two decision problems on sparse graphs.

If this is right

  • The two decision problems are at least as hard as all-pairs distance computation on sparse graphs.
  • Planarity of the host graph permits a subquadratic algorithm for both decisions.
  • Bounded treewidth of the host graph permits a near-linear algorithm for both decisions.
  • When the host graph is plane and the subgraph is delimited by a constant number of cycles, both decisions can be made in near-linear time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar quadratic barriers may exist for other distance-preservation properties of subgraphs.
  • Implementations in network or map applications could exploit planarity or low treewidth to avoid the general quadratic cost.
  • The reduction technique might extend to additional graph classes that possess exploitable structure.

Load-bearing premise

That all-pairs distances cannot be computed in subquadratic time on sparse graphs.

What would settle it

An algorithm that correctly decides both problems in O(n^{2-ε}) time for some constant ε>0 on every sparse graph with Θ(n) edges would refute the central negative claim.

read the original abstract

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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies two problems: given G and subgraph H, decide if H is isometric (distance-preserving) or geodesically convex in G. Both are solvable via all-pairs shortest paths. The central results are a conditional lower bound that neither problem admits O(n^{2-ε}) time on sparse n-vertex graphs (under a standard fine-grained hypothesis), together with subquadratic algorithms on planar graphs, near-linear algorithms on bounded-treewidth graphs, and a near-linear algorithm when G is plane and H is delimited by a constant number of cycles.

Significance. The conditional lower bound, if the reduction is correct, shows that the all-pairs baseline is essentially optimal for general sparse graphs and thereby tightens our understanding of distance-based subgraph problems. The algorithmic results for planar graphs, bounded treewidth, and the special plane-graph case supply concrete improvements that are likely to be useful in practice.

minor comments (2)
  1. [Abstract] Abstract: the conditional lower bound is stated without naming the underlying hypothesis (e.g., APSP conjecture or SETH). While the full technical section presumably contains the explicit assumption and reduction, a single-sentence clarification in the abstract would improve readability.
  2. The manuscript should include a brief comparison table or paragraph contrasting the new running times with the all-pairs baseline and with prior work on related distance or convexity problems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents standard algorithmic results for deciding isometric/convex subgraphs via all-pairs distances, plus conditional lower bounds under external fine-grained assumptions (e.g., APSP conjecture) and faster algorithms for planar/bounded-treewidth cases. No equations, predictions, or derivations are shown that reduce by construction to fitted inputs or self-citations. The lower-bound claim is a reduction from a known external hypothesis, not internally derived or self-referential. This is a normal non-circular outcome for a complexity paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are visible in the provided text.

pith-pipeline@v0.9.0 · 5664 in / 1005 out tokens · 28436 ms · 2026-05-23T02:42:05.289927+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    2 Hans-Jürgen Bandelt and Victor Chepoi

    doi:10.1145/1103963.1103966. 2 Hans-Jürgen Bandelt and Victor Chepoi. Metric graph theory and geometry: a survey. In Surveys on discrete and computational geometry , volume 453 ofContemp. Math., pages 49–86. Amer. Math. Soc., Providence, RI, 2008.doi:10.1090/conm/453/08795. 3 Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in me...

    work page doi:10.1145/1103963.1103966 2008

  2. [2]

    Cabello 17 4 Joseph Berleant, Kristin Sheridan, Anne Condon, Virginia Vassilevska Williams, and Mark Bathe

    doi:10.1016/J.JCSS.2022.01.001. Cabello 17 4 Joseph Berleant, Kristin Sheridan, Anne Condon, Virginia Vassilevska Williams, and Mark Bathe. Isometric Hamming embeddings of weighted graphs.Discret. Appl. Math., 332:119–128,

    work page doi:10.1016/j.jcss.2022.01.001 2022

  3. [3]

    5 Karl Bringmann, Thore Husfeldt, and Måns Magnusson

    doi:10.1016/J.DAM.2023.02.005. 5 Karl Bringmann, Thore Husfeldt, and Måns Magnusson. Multivariate analysis of orthogonal range searching and graph distances. Algorithmica, 82(8):2292–2315, 2020.doi:10.1007/ s00453-020-00680-z. 6 Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorith...

    work page doi:10.1016/j.dam.2023.02.005 2023

  4. [4]

    11 Victor D. Chepoi. Isometric subgraphs of Hamming graphs and d-convexity.Cybernetics (Kibernetyka), 24:6–11, 1988.doi:10.1007/BF01069520. 12 Jongmin Choi, Sergio Cabello, and Hee-Kap Ahn. Maximizing dominance in the plane and its applications. Algorithmica, 83(11):3491–3513, 2021.doi:10.1007/s00453-021-00863-2. 13 Debarati Das, Evangelos Kipouridis, Max...

    work page doi:10.1007/bf01069520 1988

  5. [5]

    16 Guillaume Ducoffe, Michel Habib, and Laurent Viennot

    doi:10.1016/j.disc.2008.04.020. 16 Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik- Chervonenkis dimension.SIAM J. Comput., 51(5):1506–1534, 2022.doi:10.1137/20M136551X. 17 David Eppstein. Recognizing partial cubes in quadratic ti...

    work page doi:10.1016/j.disc.2008.04.020 2008

  6. [6]

    On the compl exity of k-sat

    24 Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT.J. Comput. Syst. Sci., 62(2):367–375, 2001.doi:10.1006/jcss.2000.1727. 18 Testing Whether a Subgraph is Convex or Isometric 25 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. , 63(4):512–530, 2001.doi:...

    work page doi:10.1006/jcss.2000.1727 2001

  7. [7]

    A convexity lemma and expansion procedures for bipartite graphs

    26 Wilfried Imrich and Sandi Klavžar. A convexity lemma and expansion procedures for bipartite graphs. Eur. J. Comb. , 19(6):677–685, 1998.doi:10.1006/eujc.1998.0229. 27 Wilfried Imrich, Sandi Klavžar, and Henry Martyn Mulder. Median graphs and triangle-free graphs. SIAM J. Discret. Math. , 12(1):111–118, 1999.doi:10.1137/S0895480197323494. 28 Wilfried Im...

    work page doi:10.1006/eujc.1998.0229 1998

  8. [8]

    31 Philip N. Klein. Multiple-source shortest paths in planar graphs. InACM-SIAM Symposium on Discrete Algorithms, SODA 2005 , pages 146–155. SIAM,

    work page 2005

  9. [9]

    32 Hung Le and Christian Wulff-Nilsen

    URL:http://dl.acm.org/ citation.cfm?id=1070432.1070454. 32 Hung Le and Christian Wulff-Nilsen. VC set systems in minor-free (di)graphs and applications. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 5332–5360, 2024.doi:10.1137/1.9781611977912.192. 33 Tilen Marc and Lovro Šubelj. Convexity in complex networks.Netw. Sci....

    work page doi:10.1137/1.9781611977912.192 2024

  10. [10]

    34 Henry Martyn Mulder and Alexander Schrijver

    doi:10.1017/nws.2017.37. 34 Henry Martyn Mulder and Alexander Schrijver. Median graphs and Helly hypergraphs.Discret. Math., 25(1):41–50, 1979.doi:10.1016/0012-365X(79)90151-1. 35 Martyn Mulder. The structure of median graphs. Discret. Math., 24(2):197–204,

    work page doi:10.1017/nws.2017.37 2017

  11. [11]

    36 Ladislav Nebeský

    doi:10.1016/0012-365X(78)90199-1. 36 Ladislav Nebeský. Median graphs.Commentationes Mathematicae Universitatis Carolinae , 12(2):317–325,

    work page doi:10.1016/0012-365x(78)90199-1

  12. [12]

    38 Ignacio M

    doi:10.1007/978-1-4614-0797-3_5. 38 Ignacio M. Pelayo.Geodesic convexity in graphs . SpringerBriefs in Mathematics. Springer, New York, 2013.doi:10.1007/978-1-4614-8699-2. 39 Seth Pettie and Vijaya Ramachandran. Computing shortest paths with comparisons and additions. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages...

    work page doi:10.1007/978-1-4614-0797-3_5 2013

  13. [13]

    URL: http://dl.acm.org/citation.cfm?id=545381. 545417. 40 Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. InSymposium on Theory of Computing Conference, STOC’13, pages 515–524. ACM, 2013.doi:10.1145/2488608.2488673. 41 Kristin Sheridan, Joseph Berleant, Mark Bathe, Anne Condon, an...

    work page doi:10.1145/2488608.2488673 2013

  14. [14]

    Cabello 19 45 Mikkel Thorup

    URL:https://proceedings.neurips.cc/paper_files/paper/2021/ file/c4bf1e24f3e6f92ca9dfd9a7a1a1049c-Paper.pdf. Cabello 19 45 Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46(3):362–394, 1999.doi:10.1145/316542.316548. 46 Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its...

    work page doi:10.1145/316542.316548 2021