Halfspace separation in geodesic convexity
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908974244167680 |
|---|---|
| author | Nair, Niranjan |
| author_facet | Nair, Niranjan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16159 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Halfspace separation in geodesic convexity Nair, Niranjan Discrete Mathematics Combinatorics 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. |
| title | Halfspace separation in geodesic convexity |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2604.16159 |