On the approximability of graph visibility problems

Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph G of n vertices asks to find the largest set of vertices X ⊆ V ( G ), also called μ -set, such that for any two vertices u, v ∈ X , there is a shortest u, v -path P where all internal vertices of P are not in X . This means that u and v are visible w.r.t. X . Variations of this problem are known as total, outer , and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside X . The mutual-visibility problem and all its variants are known to be NP -complete on graphs of diameter 4. We design a polynomial-time algorithm that finds a μ -set of size Ω ( n / D ) , where D is the average distance in G , we show inapproximability results for all visibility problems on graphs of diameter 2, and we strengthen the inapproximability ratios for graphs of diameter 3 or larger. More precisely, assuming P ≠ NP , the mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n 1 / 3 − ε on graphs of diameter at least 3, while the outer and total mutual-visibility problems are not approximable within a factor of n 1 / 2 − ε , for any constant ε > 0. Finally, we study the relationship between the mutual-visibility number and the general position number, in which no three distinct vertices u, v, w of X belong to any shortest path of G .