Kolja Knauer ; Nicolas Nisse - Computing metric hulls in graphs

dmtcs:4720 - Discrete Mathematics & Theoretical Computer Science, May 23, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-11
Computing metric hulls in graphsArticle

Authors: Kolja Knauer ORCID1,2,3; Nicolas Nisse ORCID4

  • 1 Laboratoire d'Informatique et Systèmes
  • 2 Laboratoire d'Informatique et des Systèmes
  • 3 Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon)
  • 4 Combinatorics, Optimization and Algorithms for Telecommunications

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.


Volume: vol. 21 no. 1, ICGT 2018
Published on: May 23, 2019
Accepted on: May 15, 2019
Submitted on: July 30, 2018
Keywords: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Funding:
    Source : OpenAIRE Graph
  • Théorie métrique des graphes; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0015
  • Graphes, Algorithmes et TOpologie; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0009

Consultation statistics

This page has been seen 529 times.
This article's PDF has been downloaded 296 times.