Half-space separation in monophonic convexity
<|reference_start|>Half-space separation in monophonic convexity: 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 $\mathbf{NP}$-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity.<|reference_end|>
@article{elaroussi2024half-space,
    title={Half-space separation in monophonic convexity},
    author={Mohammed Elaroussi, Lhouari Nourine, and Simon Vilmin},
    journal={arXiv preprint arXiv:2404.17564},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.17564},
    primaryClass={math.CO cs.DM cs.DS}
}