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?

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


Your Answer

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