Computing metric hulls in graphs

Kolja Knauer 1 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 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 deciding if the smallest preimage of a closed set is logarithmic in the size of the ground set is LOGSNP-hard if only the ground set is given. A special instance of this problem is to compute the dimension of a poset given its linear extension graph, that is 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/hal-01612515
Contributor : Nicolas Nisse <>
Submitted on : Thursday, April 11, 2019 - 3:54:28 PM
Last modification on : Saturday, April 13, 2019 - 1:24:49 AM

File

DMTCS_Hull_revisedVersionbis.p...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01612515, version 3

Citation

Kolja Knauer, Nicolas Nisse. Computing metric hulls in graphs. [Research Report] Inria - Sophia Antipolis. 2017. ⟨hal-01612515v3⟩

Share

Metrics

Record views

100

Files downloads

193