Computing metric hulls in graphs

zbMATH Open1417.05218arXiv1710.02958MaRDI QIDQ5226831FDOQ5226831

Authors: Kolja Knauer, Nicolas Nisse 

Publication date: 1 August 2019

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 $Sigm{a}_2^P$ complete.

Full work available at URL: https://arxiv.org/abs/1710.02958

Recommendations

• On the computation of the hull number of a graph
• On the hull number of some graph classes
• On the hull number of some graph classes
• Convexity in partial cubes: the hull number
• Convexity in partial cubes: the hull number

zbMATH Keywords

complexityconvex hull in graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (1)

• Computing linear systems on metric graphs

This page was built for publication: Computing metric hulls in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226831)