Skip to Main content Skip to Navigation
Conference papers

On the approximation hardness of geodetic set and its variants

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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03328636
Contributor : Tom Davot Connect in order to contact the contributor
Submitted on : Wednesday, November 24, 2021 - 1:59:04 PM
Last modification on : Friday, November 26, 2021 - 3:46:01 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

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. pp.76-88, ⟨10.1007/978-3-030-89543-3_7⟩. ⟨lirmm-03328636v2⟩

Share

Metrics

Record views

41

Files downloads

7