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

Given a graph G , the P 3 -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 P 3 -Helly-independent (resp. P 3 ⁎ -Helly-independent) of a graph G is a set S ⊆ V (G) such that the intersection of the P 3 -convex hulls (P 3 ⁎ -convex hulls) of S \ { v } (∀ v ∈ S) is empty. We denote by P 3 -Helly number (resp. P 3 ⁎ -Helly number) the size of a maximum P 3 -Helly-independent (resp. P 3 ⁎ -Helly-independent). The edge counterparts of these two P 3 -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 P 3 -Helly number (resp. P 3 ⁎ -Helly number, edge P 3 -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. [ABSTRACT FROM AUTHOR]