{"id":"arxiv/2604.16159","url":"https://arxiv.org/abs/2604.16159","tags":["cs.DM","math.CO"],"score":0,"title":"Halfspace separation in geodesic convexity","domain":"cs.DM","source":"arxiv","authors":["Niranjan Nair"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-17","reactions":{}}