# Efficient algorithm for finding segregators in a directed acyclic graph

Given a directed acyclic graph $$G=(V,E)$$, we define a $$(\alpha,\beta)$$-segregator of $$G$$ to be a subset $$S$$ of $$V$$ of size $$\alpha$$ such that no vertex in $$G\setminus S$$ has more than $$\beta$$ ancestors in $$G\setminus S$$. By "ancestor of a vertex $$v$$ in $$G\setminus S$$", I mean any vertex $$u$$ for which there is a path from $$u$$ to $$v$$ that contained in $$G\setminus S$$.

I am curious as to whether there is an algorithm which, given a graph $$G$$ and a value of $$\alpha$$, returns the minimum value of $$\beta$$ such that a $$(\alpha,\beta)$$-segregator exists for $$G$$. Is the decision problem of whether a given $$(\alpha,\beta)$$-segregator exists in a graph $$G$$ known to be NP-complete? Are there at least good approximation algorithms to the problem of finding whether a graph has "good" segregators?

• This sounds like finding small separators which separate the graph into small connected components. Is that correct? Apr 29, 2020 at 11:49
• @Daniel Segregators are actually generalizations of separators. All good separators are good segregators, but not vice versa. Apr 29, 2020 at 19:21