1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user1246462 Oct 26 at 15:09
  • 1
    $\begingroup$ We may assume that the incidence graph of the Set Cover instance is connected. In that case the reduction produces a connected DAG. $\endgroup$ – Christian Komusiewicz Oct 26 at 15:13
  • $\begingroup$ Is it similarly hard to solve connected Set Cover? $\endgroup$ – user1246462 Oct 26 at 15:26
  • 2
    $\begingroup$ Yes; since one may solve each connected component independently of the others. $\endgroup$ – daniello Oct 26 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.