Open Research Index

The disjoint separators problem in graphs

Thomas Delépine, Florian Galliot, Yannick Mogge, Leandro Montero, Nicolas Schivre

arXivarxiv/2607.03603Jul 3, 2026cs.DMscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.03603
curl -X POST /api/v1/records/arxiv/2607.03603/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.03603/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'