<p>In this answer i assume that <span class="math-container">$u$</span> is an ancestor of <span class="math-container">$v$</span> if <span class="math-container">$u$</span> can reach <span class="math-container">$v$</span> by a directed path.</p>
<p>This is basically as hard as Set Cover (Given family <span class="math-container">$F$</span> over a universe <span class="math-container">$U$</span>, find smallest subfamily <span class="math-container">$F’$</span> of <span class="math-container">$F$</span> whose union is <span class="math-container">$U$</span>). To reduce from Set Cover:</p>
<p>Make a vertex for every set in <span class="math-container">$F$</span> and for every element in <span class="math-container">$U$</span>. Make an arc from every element to every set that contains it.</p>
<p>Now picking a list corresponding to a set means deleting the set and all the elements in it.</p>
<p>For every element add some new dummy vertices and add arcs from each element to its own private dummy vertices.</p>
<p>Now observe that as long as all elements have not been deleted there are still components of more than <span class="math-container">$O(1)$</span> vertices left - an element plus its dummies.</p>

CC BY-SA 4.0
2020-10-26T15:09:38.890Z
Ah sorry, I'll accept your answer but I actually meant to ask about initial graphs that are *connected* meaning there exists only a single component in the original graph. Not sure what is the best sway to ask this question...edit the original question?
user1246462
CC BY-SA 4.0
2020-10-26T15:13:09.813Z
We may assume that the incidence graph of the Set Cover instance is connected. In that case the reduction produces a connected DAG.
Christian Komusiewicz
CC BY-SA 4.0
2020-10-26T15:26:23.973Z
Is it similarly hard to solve connected Set Cover?
user1246462
CC BY-SA 4.0
2020-10-26T16:35:04.563Z
Yes; since one may solve each connected component independently of the others.
daniello
CC BY-SA 4.0
2020-10-26T06:49:19.160Z
2020-10-26T06:49:19.160Z
daniello
<p>Suppose we are given a DAG, <span class="math-container">$G = (V, E)$</span> where <span class="math-container">$n = |V|$</span>. We consider the sets <span class="math-container">$J_1, J_2, \dots, J_n$</span> to be lists of vertices where list <span class="math-container">$J_i$</span> consists of vertex <span class="math-container">$v_i \in V$</span> and <strong>all ancestors</strong> of <span class="math-container">$v_i$</span>. I want to find a set of lists <span class="math-container">$\mathcal{J}$</span> such that removing all vertices in <span class="math-container">$\mathcal{J}$</span> from <span class="math-container">$G$</span> results in <strong>disjoint</strong> subgraphs where each subgraph has at most <span class="math-container">$O(1)$</span> vertices. Has anyone seen an algorithm in any work that solves this problem and finds a minimum number of lists in <span class="math-container">$\mathcal{J}$</span> efficiently? It also seems to me that there exists a <span class="math-container">$\mathcal{J}$</span> for any DAG <span class="math-container">$G$</span> that has size <span class="math-container">$O(\log n)$</span> always. This seems like a question that should be closely related to finding balanced separators but I haven't seen anything yet in this literature regarding this specific or a closely related problem.</p>

<ds.algorithms><graph-theory><graph-algorithms><ds.data-structures><directed-acyclic-graph>
Separating DAGs using separators consisting of lists of nodes and all ancestors
user1246462
# Separating DAGs using separators consisting of lists of nodes and all ancestors

(Asked by: username_0 on 2020-10-25)

Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J\_1, J\_2, \dots, J\_n$ to be lists of vertices where list $J\_i$ consists of vertex $v\_i \in V$ and **all ancestors** of $v\_i$. I want to find a set of lists $\mathcal{J}$ such that removing all vertices in $\mathcal{J}$ from $G$ results in **disjoint** subgraphs where each subgraph has at most $O(1)$ vertices. Has anyone seen an algorithm in any work that solves this problem and finds a minimum number of lists in $\mathcal{J}$ efficiently? It also seems to me that there exists a $\mathcal{J}$ for any DAG $G$ that has size $O(\log n)$ always. This seems like a question that should be closely related to finding balanced separators but I haven't seen anything yet in this literature regarding this specific or a closely related problem.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, ds.data-structures, directed-acyclic-graph


---

## 1 answers

### Answer by username_1 on 2020-10-26. Score: 4 | Accepted answer

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.

This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover:

Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to every set that contains it.

Now picking a list corresponding to a set means deleting the set and all the elements in it.

For every element add some new dummy vertices and add arcs from each element to its own private dummy vertices.

Now observe that as long as all elements have not been deleted there are still components of more than $O(1)$ vertices left - an element plus its dummies.

> **Comments:**
> **username_0**: Ah sorry, I'll accept your answer but I actually meant to ask about initial graphs that are *connected* meaning there exists only a single component in the original graph. Not sure what is the best sway to ask this question...edit the original question?  
> **username_2**: We may assume that the incidence graph of the Set Cover instance is connected. In that case the reduction produces a connected DAG.  
> **username_0**: Is it similarly hard to solve connected Set Cover?  
> **username_1**: Yes; since one may solve each connected component independently of the others.  

---

