S₄ Separation and p-partition in all-path and detour convexities

Abstract

In this work, we consider problems of S₄ and p-convex partition separations with respect to the all-path and the detour convexities. We give characterizations of p-all-path convex and p-detour convex graphs. With respect to all-path convexity S₂, S₃, and S₄ separable graphs are characterized. Also, we present necessary and sufficient conditions for two sets to be S4 separable, for both convexities. Moreover, we prove that in all-path convexity the time complexity of those problems is linear, and it is NP-hard for detour convexity. Finally, we give an algorithm for determining whether two sets in graph are S₄ separable with respect to all-path convexity.