The convexity of induced paths of order three and applications; Complexity aspects

摘要

In this paper, we introduce a new convexity on graphs similar to the well known P-3-convexity, which we will call P*(3)-convexity. We show that several P*(3)-convexity parameters (hull number, convexity number, Caratheodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P-3-convexity is NP-hard even for subgraphs of grids and that the convexity number for the P-3-convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P-4-sparse graphs. (C) 2017 Elsevier B.V. All rights reserved.