# Enumerating Minimal (a,b) vertex separators in a DAG

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.

• 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. – Hermann Gruber Sep 24 '19 at 20:20