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

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.

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.

• 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 Oct 26 '20 at 15:09
• 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 Oct 26 '20 at 15:13
• Is it similarly hard to solve connected Set Cover? – user1246462 Oct 26 '20 at 15:26
• Yes; since one may solve each connected component independently of the others. – daniello Oct 26 '20 at 16:35