3
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Sep 24, 2019 at 20:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.