Haponenko, Vladyslav2026-06-012026-06-012026Haponenko V. S4 separation and p-partition in all-path and detour convexities / V. Haponenko // TWMS Journal of Applied and Engineering Mathematics. - 2026. - Vol. 16, Issue 4. - P. 443-456. - https://jaem.isikun.edu.tr/web/index.php/current/142-vol16no4/1579-s4-separation-and-p-partition-in-all-path-and-detour-convexities2587-1013https://ekmair.ukma.edu.ua/handle/123456789/39871In 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.en-USall-path convexitygraph convexitydetour convexityconvex separationp-partitionarticleArticle