1
$\begingroup$

I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies.

My goal is to find the smallest subset of targets that, if I remove all of their dependencies, breaks all of the cycles, leaving me with a buildable dependency tree.

This sounds very much like a well-understood graph problem to me, but I can't figure out which one. I'm afraid it also smells like an NP complete problem, but I'm hoping there's a good trick that I've missed. Can someone suggest what the name of this problem might be so that I can read a bit more about it, or what a good approach to solving it could be?

$\endgroup$
1
$\begingroup$

Decompose your graph into strongly connected components. Now each strongly-connected component (SCC) of size $>1$ contains a cycle.

Let $G=(V,E)$ be the dag of SCCs obtained by this decomposition. Sometimes $G$ is called "the metagraph". Let $S \subseteq V$ be the set of SCCs of size $>1$. Now our algorithmic problem is as follows:

Given the dag $G$ and the set $S$, find a minimum-size set $T \subseteq V$ such that for every $v \in S$, there's a path from $v$ to some vertex of $T$.

The rest of the answer below is incorrect, but I'll leave the problem statement above in case it helps someone else find a clean algorithm.


This problem can be solved using a network flow algorithm.

In particular, this problem can in turn be rephrased as something akin to a minimum-cut problem: if we add a source vertex $s$ with an edge to each vertex of $S$ and a sink vertex $t$ with an edge from each vertex of $T$ to $t$, we want to find a minimum-size set of vertices that completely disconnect $s$ from $t$. Notice that this isn't quite the normal minimum-cut problem, because here we care about minimizing the number of selected vertices rather than minimizing the cost of the edges that cross the cut, but it's close.

Here's how we can solve this problem. For each vertex $v \in V$, we add two vertices $v_\text{in},v_\text{out}$, and we add an edge with cost 1 from $v_\text{in}$ to $v_\text{out}$. Also, we replace each edge $(v,w) \in E$, with the edge $(v_\text{out}, w_\text{in})$, and we make this edge have cost $\infty$. We add a source vertex $s$ and, for each $v \in S$, we add a source vertex $s$ and an edge of capacity $\infty$ from $s$ to $v_\text{in}$. We also add a sink vertex $t$ and, for each $v \in V$, we add an edge of capacity $1$ from $v_\text{out}$ to $t$. Let $G'=(V',E')$ be the resulting graph.

Finally, we find a minimum $(s,t)$-cut in $G'$. This can be done by using a standard network flow algorithm to compute the maximum $(s,t)$-flow, and then using the Ford-Fulkerson min-cut/max-flow theorem to reconstruct a minimum $(s,t)$-cut. Suppose the cut is $(U,V'\setminus U)$, where $s \in U$ and $t \notin U$. Then for each vertex $v \in V$ such that $v_\text{in} \in U$ and $v_\text{out} \notin U$, we add $v$ to $T$. This gives us a set $T$ of vertices that, in $G$, disconnect $s$ from $t$, and by construction, the size of $T$ is minimal.

$\endgroup$
1
$\begingroup$

I have some thoughts about complexity of this task. First of all let's rephrase original task:

Given the graph $G=(V,E)$ with only 1 SCC, find the biggest subset of vertexes $R \subseteq V $ such that it forms DAG.

In case when we have more that 1 SCC we can break original graph on subgraphs that contans only 1 SSC (as shown in answer above) and solve task for each subgraph independently.

Let's call $t_i$ - will we take vertex $i$ to resulting graph or not. Now we able to write some implications using $t_i$, for example:

graph

$$ t_a \land t_b \to \overline{t_d}\hspace{10pt}(1)\\ t_a \land t_c \to \overline{t_d}\hspace{10pt}(2)\\ ... $$

$(1)$ means if we will take to result graph vertexes $A, B$ we can not take vertex $D$. And, of course, we can have more such implications.

We can rewrite each implication in another form: $$ t_{i_1} \land t_{i_2} \land ... \land t_{i_{n-1}} \to \overline{t_{i_n}}\\ \overline{t_{i_1} \land t_{i_2} \land ... \land t_{i_{n-1}}} \lor \overline{t_{i_n}}\\ \overline{t_{i_1}} \lor \overline{t_{i_2}} \lor ... \lor \overline{t_{i_{n-1}}} \lor \overline{t_{i_n}}\\ $$

And here we have Boolean satisfiability problem that can be solved in $linear$ time iff implication is of form $a \to b$ (e.g. only 2 variables in equation, it's called 2-SAT problem). In case when more that 2 variables are used in equations it is NP-complete.

$\endgroup$
  • $\begingroup$ I don't think you've rephrased the original problem accurately. The problem isn't to find a subset of nodes that forms a dag; the problem is to find a set of nodes $T$ such that, if you remove every node that can reach a node in $T$, the result will be a dag. That's not the same. Also, nothing in it promises that there will be exactly 1 SCC, and your strategy for handling graphs with more than 1 SCC seems incorrect: if we have a graph with two vertices $A,B$ and one edge $A \to B$, the correct answer is to output "B", but your algorithm doesn't produce that. $\endgroup$ – D.W. Jul 20 '15 at 8:33

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.