Halfspace separation in geodesic convexity

2026/04/17 by Niranjan Nair · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2604.16159

Abstract

Let G = V, E be a simple connected undirected graph. A set X ⊆ V is geodesically convex if for any pair of vertices x, y ∈ X, all vertices on all shortest paths in G from x to y are contained in X. A set H ⊆ V is said to be a halfspace if both H and its complement (denoted by H^c) are convex. Given two sets A, B ⊆ V, the halfspace separation problem asks if there exist complementary halfspaces H, H^c such that A ⊆ H and B ⊆ 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.

Citations

• Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
• Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
• Half-space separation in monophonic convexity
• Maximal Closed Set and Half-Space Separations in Finite Closure Systems
• A combinatorial non-positive curvature I: weak systolicity
• On two conjectures of Maurer concerning basis graphs of matroids
• Dismantlability of weakly systolic complexes and applications
• Six theorems about injective metric spaces
• Separation axiom S₃ for geodesic convexity in graphs
• Metric graph theory and geometry: a survey

Discussions

• Niranjan Nair: Halfspace separation in geodesic convexity https://arxiv.org/abs/2604.16159 https://arxiv.org/pdf/2604.16159 https://arxiv.org/html/2604.16159 [bsky, 0 points, 0 comments]

Related

• Separation axiom S₃ for geodesic convexity in graphs
• Half-space separation in monophonic convexity
• On the Geodetic Hull Number of Complementary Prisms
• Hull and Geodetic Numbers for Some Classes of Oriented Graphs
• Hardness and structural results for half-squares of restricted tree convex bipartite graphs