{"id":"arxiv/2610.19093","url":"https://arxiv.org/abs/2610.19093","tags":["math.CO","cs.DS"],"score":0,"title":"Finding non-bisimplicial and triad-free minimal separators","domain":"math.CO","source":"arxiv","authors":["Maria Chudnovsky","Ilya Maier"],"reviews":0,"subject":"math.CO","summary":"A $u\\hbox{-}v$ separator in $G$ is a set $S\\subseteq V(G)\\setminus\\{u,v\\}$ such that there is no $u\\hbox{-}v$ path in $G\\setminus S$. A minimal separator in $G$ is a set $S$ such that for some $u,v\\in V(G)\\setminus S$, $S$ is a $u\\hbox{-}v$ separator in $G$ but no proper subset of $S$ is. A set $S$ is bisimplicial if it is the union of at most two cliques. Recognizing graphs in which every minimal separator is the union of at most $k$ cliques is polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\\geq 3$. We settle the remaining case $k=2$ by giving a polynomial-time algorithm…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}