Skip to Main content Skip to Navigation
New interface
Journal articles

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 :
Journal articles
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-01612515
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Thursday, May 23, 2019 - 1:32:32 PM
Last modification on : Thursday, August 4, 2022 - 4:58:26 PM

File

DMTCS_MetricHull_Final.pdf
Files produced by the author(s)

Identifiers

Citation

Kolja Knauer, Nicolas Nisse. Computing metric hulls in graphs. Discrete Mathematics and Theoretical Computer Science, 2019, vol. 21 no. 1, ICGT 2018, ⟨10.23638/DMTCS-21-1-11⟩. ⟨hal-01612515v4⟩

Share

Metrics

Record views

521

Files downloads

851