Bisimplicial and triad-free minimal separator recognition problem
Given a finite graph , decide whether every minimal separator of is bisimplicial, that is, whether for every set such that there exist distinct vertices for which separates and in and no proper subset of does, there exist cliques of with . Determine whether this recognition problem can be solved in polynomial time.
References
- Finding non-bisimplicial and triad-free minimal separators — arXiv — Maria Chudnovsky, Ilya Maier
Source: arXiv
Progress summary
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 - separator with independence number at most . Both cases were previously unresolved between the polynomial-time cases and NP-hardness for fixed .
Known results
- Recognition is polynomial-time solvable for .
- Recognition is NP-hard for every fixed .
- The December 17, 2023 paper reported the 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 questions: recognizing whether every minimal separator is bisimplicial, and finding a separator with independence number at most , or certifying that none exists. No independent mathematical assessment, correction, or referee report was found.
Current status (as of October 2026): The two cases are claimed solved by an unrefereed preprint, but remain unverified; the surrounding and fixed complexity results are established.
Solutions 0
No solutions have been posted yet.