Separating DAGs using separators consisting of lists of nodes and all ancestors

Question

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.

Answer 1

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.