On the Computational Complexity of the Helly Number in the P3 and Related Convexities

Given a graph G, the P3-convex hull (resp. P 3 ⁎ -convex hull) of a set C ⊆ V (G) is obtained by iteratively adding to C vertices with at least two neighbors inside C (resp. at least two non-adjacent neighbors inside C). A P3-Helly-independent (resp. P 3 ⁎ -Helly-independent) of a graph G is a set S ⊆ V (G) such that the intersection of the P3-convex hulls ( P 3 ⁎ -convex hulls) of S \ {v} (∀v ∈ S) is empty. We denote by P3-Helly number (resp. P 3 ⁎ -Helly number) the size of a maximum P3-Helly-independent (resp. P 3 ⁎ -Helly-independent). The edge counterparts of these two P3-Helly-independents follow the same restrictions applied to its edges. The vp 3 hi (resp. vsp 3 hi , ep 3 hi , and esp 3 hi ) problem aims to determine the P3-Helly number (resp. P 3 ⁎ -Helly number, edge P3-Helly number, and edge P 3 ⁎ -Helly number) of a graph. We establish the computational complexities of vp 3 hi , vsp 3 hi , ep 3 hi , and esp 3 hi for a collection of graph classes, including bipartite graphs, split graphs, and join of graphs.