Geodesic
Computing metric hulls in graphs
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_1_a7,
     author = {Knauer, Kolja and Nisse, Nicolas},
     title = {Computing metric hulls in graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-11/}
}
TY  - JOUR
AU  - Knauer, Kolja
AU  - Nisse, Nicolas
TI  - Computing metric hulls in graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-11/
DO  - 10.23638/DMTCS-21-1-11
LA  - en
ID  - DMTCS_2019_21_1_a7
ER  - 
%0 Journal Article
%A Knauer, Kolja
%A Nisse, Nicolas
%T Computing metric hulls in graphs
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-11/
%R 10.23638/DMTCS-21-1-11
%G en
%F DMTCS_2019_21_1_a7
Knauer, Kolja; Nisse, Nicolas. Computing metric hulls in graphs. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi : 10.23638/DMTCS-21-1-11. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-11/

Cité par Sources :