S4 SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES

S4 SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES

V. Haponenko

[PDF]

Abstract

In this work, we consider problems of S4 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 S2, S3, and S4 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 S4 separable with respect to all-path convexity.

Keywords

all-path convexity, graph convexity, detour convexity, convex separation, p-partition.