Inapproximability results for graph convexity parameters

In this paper, we prove several inapproximability results on the P3P3-convexity and the geodesic convexity in graphs. We prove that determining the P3P3-hull number and the geodetic hull number are APX-hard problems. We prove that the Carathéodory number, the Radon number and the convexity number of both convexities are O(n1−ε)O(n1−ε)-inapproximable in polynomial time for every ε>0ε>0, unless P=NPP=NP. We also prove that the interval numbers of both convexities are W[2]W[2]-hard and O(log⁡n)O(log⁡n)-inapproximable in polynomial time, unless P=NPP=NP. Moreover, these results hold for bipartite graphs in the P3P3-convexity.