Title: Computing metric hulls in graphs,
Abstract: We prove that, given a closure function the smallest preimage of a closed set
can be calculated in polynomial time in the number of closed sets. This
confirms a conjecture of Albenque and Knauer and implies that there is a
polynomial time algorithm to compute the convex hull-number of a graph, when
all its convex subgraphs are given as input. We then show that computing if the
smallest preimage of a closed set is logarithmic in the size of the ground set
is LOGSNP-complete if only the ground set is given. A special instance of this
problem is computing the dimension of a poset given its linear extension graph,
that was conjectured to be in P.
The intent to show that the latter problem is LOGSNP-complete leads to
several interesting questions and to the definition of the isometric hull,
i.e., a smallest isometric subgraph containing a given set of vertices $S$.
While for $|S|=2$ an isometric hull is just a shortest path, we show that
computing the isometric hull of a set of vertices is NP-complete even if
$|S|=3$. Finally, we consider the problem of computing the isometric
hull-number of a graph and show that computing it is $\Sigma^P_2$ complete.