Title
The convexity of induced paths of order three and applications: Complexity aspects.
Abstract
In this paper, we introduce a new convexity on graphs similar to the well known P3-convexity, which we will call P3∗-convexity. We show that several P3∗-convexity parameters (hull number, convexity number, Carathéodory 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 P3-convexity is NP-hard even for subgraphs of grids and that the convexity number for the P3-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 P4-sparse graphs.
Year
DOI
Venue
2018
10.1016/j.dam.2017.11.007
Discrete Applied Mathematics
Keywords
Field
DocType
Graph convexity,Geodesic convexity,Algorithms,Complexity
Graph,Discrete mathematics,Combinatorics,Convexity,Geodesic convexity,Hull number,Bipartite graph,Time complexity,Percolation,Mathematics
Journal
Volume
ISSN
Citations 
237
0166-218X
0
PageRank 
References 
Authors
0.34
9
4