On finite convexity spaces induced by sets of paths in graphs

AbstractA finite convexity space is a pair (V,C) consisting of a finite set V and a set C of subsets of V such that 0̸∈C, V∈C, and C is closed under intersection. A graph G with vertex set V and a set P of paths of G naturally define a convexity space (V,C(P)) where C(P) contains all subsets C of V such that whenever C contains the endvertices of some path P in P, then C contains all vertices of P.We prove that for a finite convexity space (V,C) and a graph G with vertex set V, there is a set P of paths of G with C=C(P) if and only if •every set S which is not convex with respect to C contains two distinct vertices whose convex hull with respect to C is not contained in S and•for every two elements x and z of V and every element y distinct from x and z of the convex hull of {x,z} with respect to C, the subgraph of G induced by the convex hull of {x,z} with respect to C contains a path between x and z with y as an internal vertex. Furthermore, we prove that the corresponding algorithmic problem can be solved efficiently