On the approximation hardness of geodetic set and its variants - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2021

On the approximation hardness of geodetic set and its variants

Tom Davot
Lucas Isenmann
  • Function : Author
  • PersonId : 1108593

Abstract

Given a graph, a geodetic set (resp. edge geodetic set) is a subset of vertices such that every vertex (resp. edge) of the graph is on a shortest path between two vertices of the subset. A strong geodetic set is a subset S of vertices and a choice of a shortest path for every pair of vertices of S such that every vertex is on one of these shortest paths. The geodetic number (resp. edge geodetic number) of a graph is the minimum size of a geodetic set (resp. edge geodetic set) and the strong geodetic number is the minimum size of a strong geodetic set. We first prove that, given a subset of vertices, it is N P-hard to determine whether it is a strong geodesic set. Therefore, it seems natural to study the problem of maximizing the number of covered vertices by a choice of a shortest path for every pair of a provided subset of vertices. We provide a tight 2approximation algorithm to solve this problem. Then, we show that there is no 781 /780 polynomial-time approximation algorithm for edge geodetic number and strong geodetic number on subcubic bipartite graphs with arbitrarily high girth. We also prove that geodetic number and edge geodetic number are both LOG-APX-hard, even on subcubic bipartite graphs with arbitrarily high girth. Finally, we disprove a conjecture of Iršič and Konvalinka by proving that the strong geodetic number can be computed in polynomial time in complete multipartite graphs.
Fichier principal
Vignette du fichier
main.pdf (398.47 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03328636 , version 1 (30-08-2021)
lirmm-03328636 , version 2 (24-11-2021)

Identifiers

  • HAL Id : lirmm-03328636 , version 1

Cite

Tom Davot, Lucas Isenmann, Jocelyn Thiebaut. On the approximation hardness of geodetic set and its variants. 27th International Computing and Combinatorics Conference (COCOON 2021), Oct 2021, Tainan, Taiwan. ⟨lirmm-03328636v1⟩
247 View
238 Download

Share

Gmail Mastodon Facebook X LinkedIn More