{"id":"arxiv/2607.03603","url":"https://arxiv.org/abs/2607.03603","tags":["cs.DM","math.CO"],"score":0,"title":"The disjoint separators problem in graphs","domain":"cs.DM","source":"arxiv","authors":["Thomas Delépine","Florian Galliot","Yannick Mogge","Leandro Montero","Nicolas Schivre"],"reviews":0,"subject":"cs.DM","summary":"We study the disjoint separators problem in graphs, an analogue of the famous disjoint paths problem. Given a graph $G$ and four pairwise disjoint subsets of vertices $S_r$, $T_r$, $S_b$, $T_b$, we ask whether there exist an $(S_r,T_r)$-separator and an $(S_b,T_b)$-separator which are disjoint. This is equivalent to coloring the vertices in red or blue, with $S_r \\cup T_r$ in red and $S_b \\cup T_b$ in blue, such that there is no red $(S_r,T_r)$-path and no blue $(S_b,T_b)$-path. On the one hand, we show that the disjoint separators problem is NP-complete. We actually exhibit several…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-03","reactions":{}}