Computing simple-path convex hulls in hypergraphs

In a connected hypergraph a vertex set X is simple-path convex (sp-convex  , for short) if either |X|⩽1|X|⩽1 or X contains every vertex on every simple path between two vertices in X (Faber and Jamison, 1986 [7]), and the sp-convex hull of a vertex set X is the minimal superset of X that is sp-convex. In this paper, we give a polynomial algorithm to compute sp-convex hulls in an arbitrary hypergraph.

Research highlights► Computing simple path convex hulls in hypergraphs. ► An efficient algorithm for computing simple path convex hulls in a totally balanced hypergraph. ► An efficient algorithm for computing simple path convex hulls in an arbitrary hypergraph.