# Half-space separation in monophonic convexity

arXiv: https://arxiv.org/abs/2404.17564 · HTML: https://mlsanity.com/paper/2404.17564/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2024.

## Built on by (most cited first, 2 of 2)

- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)

## Abstract (arXiv)

We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is NP-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity.