Finding non-bisimplicial and triad-free minimal separators

Abstract

A u−v separator in G is a set S⊆ V(G)∖{u,v} such that there is no u−v path in G∖ S. A minimal separator in G is a set S such that for some u,v∈ V(G)∖ S, S is a u−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≥ 3. We settle the remaining case k=2 by giving a polynomial-time algorithm to decide whether every minimal separator in a graph is bisimplicial. A set S is triad-free if its independence number α(S) is at most two. Given a graph G and two vertices u,v, the problem of finding a u−v separator S with α(S)≤ k had the same complexity gap: it was known to be polynomial-time solvable for k=1 and NP-hard for every fixed k≥ 3. We resolve the remaining case k=2 by giving a polynomial-time algorithm that finds a triad-free u−v separator or determines that none exists.

On separators in K_t-minor-free graphs
Xinheng Lin
arXiv29 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
K_h-Minor-Free Graphs Have Balanced Separators of Size O(h√n)
Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
arXiv1 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
James Davies, Paweł Rzążewski, Jack Spalding-Jamieson +1
arXiv16 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv
On the Complexity of Finding Decoherence Free Subspaces
Evan Borras
arXiv22 Sep 2026PreprintCC BY 4.0Full textMathematical physics Quantum physics & quantum informationarXiv
Inequivalent complexity criteria for free boundary minimal surfaces
Alessandro Carlotto, Giada Franz
Advances in Mathematics29 Oct 2026Peer-reviewedLicence not statedFull text1 citedGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{chudnovsky2026finding,
  title = {{Finding non-bisimplicial and triad-free minimal separators}},
  author = {Maria Chudnovsky and Ilya Maier},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.19093},
  eprint = {2610.19093},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.19093},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Finding non-bisimplicial and triad-free minimal separators
AU  - Maria Chudnovsky
AU  - Ilya Maier
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.19093
UR  - https://arxiv.org/abs/2610.19093
AB  - A u−v separator in G is a set S⊆ V(G)∖{u,v} such that there is no u−v path in G∖ S. A minimal separator in G is a set S such that for some u,v∈ V(G)∖ S, S is a u−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≥ 3. We settle the remaining case k=2 by giving a polynomial-time algorithm to decide whether every minimal separator in a graph is bisimplicial. A set S is triad-free if its independence number α(S) is at most two. Given a graph G and two vertices u,v, the problem of finding a u−v separator S with α(S)≤ k had the same complexity gap: it was known to be polynomial-time solvable for k=1 and NP-hard for every fixed k≥ 3. We resolve the remaining case k=2 by giving a polynomial-time algorithm that finds a triad-free u−v separator or determines that none exists.
ER  -

Abstract

Related

Cite