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

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

CC BY-SA 4.0
2020-04-29T11:49:18.900Z
This sounds like finding small separators which separate the graph into small connected components. Is that correct?
Daniel
CC BY-SA 4.0
2020-04-29T19:21:32.113Z
@Daniel Segregators are actually generalizations of separators. All good separators are good segregators, but not vice versa.
exfret
<cc.complexity-theory><graph-algorithms><approximation-algorithms><np-complete>
Efficient algorithm for finding segregators in a directed acyclic graph
exfret
# Efficient algorithm for finding segregators in a directed acyclic graph

(Asked by: username_0 on 2020-04-26)

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?

**Tags:** cc.complexity-theory, graph-algorithms, approximation-algorithms, np-complete
> **Comments:**
> **username_1**: This sounds like finding small separators which separate the graph into small connected components. Is that correct?  
> **username_0**: @Daniel Segregators are actually generalizations of separators. All good separators are good segregators, but not vice versa.  

---

## 0 answers

