← All problems

Bisimplicial and triad-free minimal separator recognition problem

Given a finite graph GG, decide whether every minimal separator SS of GG is bisimplicial, that is, whether for every set S⊆V(G)S\subseteq V(G) such that there exist distinct vertices u,v∈V(G)∖Su,v\in V(G)\setminus S for which SS separates uu and vv in GG and no proper subset of SS does, there exist cliques C1,C2C_1,C_2 of GG with S=C1∪C2S=C_1\cup C_2. Determine whether this recognition problem can be solved in polynomial time.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new unrefereed preprint claims polynomial-time algorithms for both previously unresolved two-clique separator cases, but the claims have not been independently checked.

The problem asks for efficient recognition of graphs whose minimal separators are unions of at most two cliques, and for efficient detection of a uu-vv separator with independence number at most 22. Both cases were previously unresolved between the polynomial-time k=1k=1 cases and NP-hardness for fixed k≥3k\geq 3.

Known results

  • Recognition is polynomial-time solvable for k=1k=1.
  • Recognition is NP-hard for every fixed k≥3k\geq 3.
  • The December 17, 2023 paper reported the k=2k=2 recognition case as open and gave structural and optimization results for the corresponding graph class.

October 2026 claimed algorithms

Maria Chudnovsky and Ilya Maier’s preprint Finding non-bisimplicial and triad-free minimal separators claims polynomial-time algorithms for both k=2k=2 questions: recognizing whether every minimal separator is bisimplicial, and finding a separator with independence number at most 22, or certifying that none exists. No independent mathematical assessment, correction, or referee report was found.

Current status (as of October 2026): The two k=2k=2 cases are claimed solved by an unrefereed preprint, but remain unverified; the surrounding k=1k=1 and fixed k≥3k\geq 3 complexity results are established.

Sources

Solutions 0

No solutions have been posted yet.