How many steps are necessary to separate a bigraph? (Q1850581)

The author presents a method to construct bigraphs in order to prove the following simple results: (1) There exist bigraphs that are deterministically separable, but in no less than \(n\) steps, for any \(n\in\mathbb{N}\). (2) There exist bigraphs that are non-deterministically separable, but in no less than 3 steps. For basis see \textit{D. Beaver}, \textit{S. Haber} and \textit{P. Winkler} [The mathematics of Paul Erdős, Vol. II, 121--135 (Algorithms Comb. 14, Springer, Berlin) (1997; Zbl 0892.05044)].