Halfspace separation in geodesic convexity

Niranjan Nair

Authors on Pith no claims yet

Pith reviewed 2026-05-10 07:41 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords geodesic convexityhalfspace separationweakly bridged graphspseudo-modular graphsmatroid basis graphspolynomial algorithmsgraph separation

0 comments

The pith

Geodesic halfspace separation is solvable in polynomial time for weakly bridged graphs, pseudo-modular graphs, and matroid basis graphs.

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

The paper proves that deciding whether two sets of vertices can be separated by complementary geodesic halfspaces is solvable in polynomial time when the graph belongs to one of three structured classes: weakly bridged graphs, pseudo-modular graphs, or the basis graphs of a matroid. This stands in contrast to the known NP-completeness of the identical decision problem on arbitrary graphs. A reader would care because these classes frequently arise in optimization, network design, and combinatorial settings, where efficient separation checks could enable practical algorithms for partitioning or clustering tasks under geodesic convexity.

Core claim

The central claim is that the halfspace separation problem for geodesic convexity, known to be NP-complete in general graphs, admits polynomial-time algorithms when the input graph is weakly bridged, pseudo-modular, or the basis graph of a matroid.

What carries the argument

Geodesic halfspaces, which are sets H such that both H and its complement are geodesically convex (every shortest path between members stays inside the set), together with the decision problem of whether given sets A and B can be separated by a complementary pair of such halfspaces.

Load-bearing premise

The input graphs are restricted to one of the three classes (weakly bridged, pseudo-modular, or matroid basis graphs) and geodesic convexity is defined in the standard way with no additional restrictions.

What would settle it

An explicit weakly bridged graph together with sets A and B for which halfspace separation requires superpolynomial time, or a proof that the problem is NP-complete on any one of the three classes, would falsify the polynomial-time claim.

Figures

Figures reproduced from arXiv: 2604.16159 by Niranjan Nair.

**Figure 1.** Figure 1: A square, a pyramid and an octahedron Theorem 8. Let (A,B) be a pair of shadow-closed osculating convex sets of a graph G and V + := V \ (A∪B). If G is weakly bridged, pseudo-modular or the basis graph of a matroid, then the following are equivalent for any partition (A +,B +) of V +: 1. H = A∪A +, Hc = B∪B + are complementary halfspaces. 2. A + = {x ∈ V + | α(ax) = 1} and B+ = {x ∈ V + | α(ax) = 0} for a … view at source ↗

**Figure 2.** Figure 2: A shadow-closed osculating pair. The grey vertices [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

read the original abstract

Let $G = V, E$ be a simple connected undirected graph. A set $X \subseteq V$ is \emph{geodesically convex} if for any pair of vertices $x, y \in X$, all vertices on all shortest paths in $G$ from $x$ to $y$ are contained in $X$. A set $H \subseteq V$ is said to be a {halfspace} if both $H$ and its complement (denoted by $H^c$) are convex. Given two sets $A, B \subseteq V$, the { halfspace separation} problem asks if there exist complementary halfspaces $H, H^c$ such that $A \subseteq H$ and $B \subseteq H^c$. The halfspace separation problem is known to be NP-complete for the geodesic convexity of general graphs. We show that geodesic halfspace separation is polynomial for weakly bridged graphs, pseudo-modular graphs, and the basis graphs of matroids.

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 / 0 minor

Summary. The paper defines geodesic convexity and halfspaces in undirected graphs, recalls that halfspace separation is NP-complete under geodesic convexity for general graphs, and claims to establish polynomial-time solvability of the problem on three specific classes: weakly bridged graphs, pseudo-modular graphs, and basis graphs of matroids.

Significance. If the claimed algorithms and proofs are correct, the result carves out three natural graph classes on which a generally intractable convexity separation task becomes tractable. This contributes to the complexity landscape of geodesic convexity and may support algorithmic applications in matroid theory and certain bridged or modular graph families.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their accurate summary of the manuscript and for recognizing the potential significance of establishing polynomial-time solvability of geodesic halfspace separation on the three specified graph classes. No specific major comments were provided in the report, so we have no individual points to address. We remain available to supply additional details or clarifications on the algorithms and proofs if the referee or editor requests them.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper asserts a polynomial-time result for geodesic halfspace separation on three specific graph classes using standard definitions of geodesic convexity and halfspaces. No equations, fitted parameters, self-citations, or ansatzes appear in the abstract or description that reduce any claim to its inputs by construction. The result is presented as an algorithmic theorem for restricted inputs, with no load-bearing self-referential steps or renamings of known results. This is the expected non-finding for a direct complexity claim on graph classes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract introduces no free parameters, additional axioms, or invented entities beyond the standard definitions of graphs, geodesic convexity, and halfspaces already present in the literature.

pith-pipeline@v0.9.0 · 5457 in / 1017 out tokens · 51313 ms · 2026-05-10T07:41:23.250185+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 3 canonical work pages

[1]

Bandelt and V

H.-J. Bandelt and V . Chepoi. Metric graph theory and geometry: A survey.Contemporary Mathematics, 0000, 1991

1991
[2]

Bandelt and V

H.-J. Bandelt and V . Chepoi. A Helly theorem in weakly modular spaces.Discr. Math., 125:25–39, 1996

1996
[3]

Bandelt and V

H.-J. Bandelt and V . Chepoi. Graphs with connected medians.SIAM Journal on Discrete Mathematics, 15(2):268–282, 2002

2002
[4]

Bandelt, H

H.-J. Bandelt, H. Mulder, and V . Soltan. Weak cartesian factorization with icosahedra, 5-wheels, and sub- hyperoctahedra as factor.Erasmus University Rotterdam, Econometric Institut Report 9455, 1994

1994
[5]

Bandelt and H

H.-J. Bandelt and H. M. Mulder. Pseudo-modular graphs.Discrete Mathematics, 62(3):245–260, 1986

1986
[6]

Bandelt and E

H.-J. Bandelt and E. Pesch. Dismantling absolute retracts of reflexive graphs.European Journal of Combina- torics, 10(3):211–220, 1989

1989
[7]

Bandelt and E

H.-J. Bandelt and E. Prisner. Clique graphs and helly graphs.Journal of Combinatorial Theory, Series B, 51(1):34–45, 1991

1991
[8]

Bénéteau, J

L. Bénéteau, J. Chalopin, V . Chepoi, and Y . Vaxès. Graphs with G p-connected medians.Math. Program., 203(1–2):369–420, Mar. 2023. 11

2023
[9]

Bressan, V

M. Bressan, V . Chepoi, E. Esposito, and M. Thiessen. Efficient algorithms for learning and compressing mono- phonic halfspaces in graphs.CoRR, abs/2506.23186, 2025

work page arXiv 2025
[10]

Bressan, E

M. Bressan, E. Esposito, and M. Thiessen. Efficient algorithms for learning monophonic halfspaces in graphs. In S. Agrawal and A. Roth, editors,The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 ofProceedings of Machine Learning Research, pages 669–696. PMLR, 2024

2023
[11]

Chalopin, M

J. Chalopin, M. Changat, V . Chepoi, and J. Jacob. First-order logic axiomatization of metric graph theory. Theoretical Computer Science, 993:114460, 2024

2024
[12]

Chalopin, V

J. Chalopin, V . Chepoi, H. Hirai, and D. Osajda. Weakly modular graphs and nonpositive curvature.Memoirs of AMS, 268(1309), 2020

2020
[13]

Chalopin, V

J. Chalopin, V . Chepoi, and D. Osajda. On two conjectures of maurer concerning basis graphs of matroids. Journal of Combinatorial Theory, Series B, 114:1–32, 2015

2015
[14]

V . Chepoi. Classification of graphs by means of metric triangles.Metody Diskret. Analiz. (in Russian), 49:75–93, 1989

1989
[15]

V . Chepoi. Separation of two convex sets in convexity structures.J. Geometry, 50:30–51, 1994

1994
[16]

V . Chepoi. Graphs of some CAT(0) complexes.Adv. Appl. Math., 24(2):125–179, 2000

2000
[17]

V . Chepoi. Basis graphs of even delta-matroids.Journal of Combinatorial Theory, Series B, 97(2):175–192, 2007

2007
[18]

V . Chepoi. Separation axiom S3 for geodesic convexity in graphs.CoRR, abs/2405.07512, 2024

work page arXiv 2024
[19]

Chepoi and D

V . Chepoi and D. Osajda. Dismantlability of weakly systolic complexes and applications.Transactions of the American Mathematical Society, 367(2):1247–1272, 2015

2015
[20]

Elaroussi, L

M. Elaroussi, L. Nourine, and S. Vilmin. Half-space separation in monophonic convexity. In R. Královic and A. Kucera, editors,49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, volume 306 ofLIPIcs, pages 51:1–51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024

2024
[21]

Farber and R

M. Farber and R. E. Jamison. On local convexity in graphs.Discrete Mathematics, 66(3):231–247, 1987

1987
[22]

Hell and I

P. Hell and I. Rival. Absolute retracts and varieties of reflexive graphs.Canadian Journal of Mathematics, 39(3):544–567, 1987

1987
[23]

J. Isbell. Six theorems about injective metric spaces.Commentarii mathematici Helvetici, 39:65–76, 1964

1964
[24]

Jawhari, D

E. Jawhari, D. Misane, and M. Pouzet. Retracts: graphs and ordered sets from the metric point of view.Contemp. Math, 57:175–226, 1986

1986
[25]

S. B. Maurer. Matroid basis graphs. I.Journal of Combinatorial Theory, Series B, 14(3):216–240, 1973

1973
[26]

D. Osajda. A combinatorial non-positive curvature I: weak systolicity.CoRR, abs/1305.4661, 2013

work page arXiv 2013
[27]

Pesch.Retracts of Graphs

E. Pesch.Retracts of Graphs. Athenaeum Verlag, Frankfurt, 1988

1988
[28]

R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5:237–252, 1975

1975
[29]

Seiffarth, T

F. Seiffarth, T. Horváth, and S. Wrobel. Maximal closed set and half-space separations in finite closure systems. Theor. Comput. Sci., 973:114105, 2023

2023
[30]

V . P. Soltan and V . Chepoi. Conditions for invariance of set diameters underd-convexification in a graph. Cybernetics (Kiev), 19:750–756, 1983. 12

1983