Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Half-space separation in monophonic convexity
(Submitted on 26 Apr 2024)
Abstract: 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.
Link back to: arXiv, form interface, contact.