A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.

$S$ is a minimal $(a,b)$ separator if no proper subset of $S$ separates $a$ and $b$.

It is known [1] that all minimal $(a,b)$ separators in an undirected connected graph can be computed in $O(n^2 R_{ab})$ time, where $R_{ab}$ is the number of minimal $(a,b)$ separators.

Question 1. Are there any results showing that this enumeration can be done more efficiently when restricted to DAGs?

Question 2. Is there a simpler algorithm than [1] to do the enumeration in a DAG?

[1] Shen, Hong, Keqin Li, and Si-Qing Zheng. "Separators are as simple as cutsets." Annual Asian Computing Science Conference. Springer, Berlin, Heidelberg, 1999.

  • $\begingroup$ The minimal (a,b)-separators in an undirected graphs admit a partial order giving rise to a complete lattice. Maybe one can exploit this, and transfer the result to acyclic digraphs. (Its a while back that I got into that.) See Escalante, F. (1972). "Schnittverbände in Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 38: 199–220. doi:10.1007/BF02996932. $\endgroup$ – Hermann Gruber Sep 24 '19 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.