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 variations are known to be NP-complete on graphs of diameter $4$. In this paper, we design a polynomial-time algorithm that finds a μ-set with size Ω( √n/ D̄ ), where D is the average distance between any two vertices of G. Moreover, we show inapproximability results for all visibility problems on graphs of diameter $2$ and strengthen the inapproximability ratios for graphs of diameter $3$ or larger. More precisely, for graphs of diameter at least $3$ and for every constant ε > 0, we show that mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n1/3-ε, while outer and total mutual-visibility problems are not approximable within a factor of n1/2 - ε, unless P=NP. Furthermore 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.