# Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks

My question stems from something mentioned in the following paper*:

Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia

Given a DAG representing a Boolean network, $N$, where each node represents a logic gate, define a k-way partitioning solution as $S = (A_1, A_2, ..., A_k)$ satisfying $$A_i \cap A_j = \emptyset \quad{\text{and,}}$$ $$\bigcup\limits_{i=1}^{k} A_i = N$$

Then define a dependency graph $D(S)$. This is a directed graph with $k$ nodes where each node represents a block, $A_i$, and has an edge $(A_i,A_j)$ if and only if there exists an edge $(x,y)$ in $N$ such that $x \in{A_i}$ and $y \in A_j$ (in other words, the edges are the edges removed when forming the partition).

The authors note that it is possible to get dependency graphs that are cyclic after some k-way partition. My question is, how is this possible? I can't seem to come up with an example where partitioning a DAG would ever produce a cyclic dependency graph. As I see it, a cyclic dependency graph would require a an edge to be "reversed" somehow, which would produce a cycle in the original DAG. Perhaps it has something to do with the fact these graphs are representing boolean networks?

*Link to pdf may be paywalled

**Note the authors also have a balance constraint on the partitions which I didn't describe but I don't think that's relevant to my question.

• Can you provide a full citation for the paper, that will work even if the link stops working, and so that others interested in the paper can find this post? I suggest including title, authors, and where published, as well as a link to a freely available PDF, if possible. We have collected some advice here. Thank you!
– D.W.
Sep 7 '17 at 22:26
• Yes that's a good point. Can't quite tell if it's paywalled (I think it might be) but I can't seem to find a link that's clearly free. Hope that suffices and thanks for pointing that out!
– jaip
Sep 8 '17 at 1:31
• No worries, there won't always be a free pdf available -- it's just a nice to have, if one exists (as it might help get you better answers, in case someone wants to read the paper).
– D.W.
Sep 8 '17 at 8:31

Consider the following graph on three vertices:

$$u \to v \to w$$

This is acyclic. If you set $A_1 = \{u,w\}$ and $A_2 = \{v\}$, you end up with a dependency graph that is cyclic: it has an edge $A_1 \to A_2$ (due to the edge $u \to v$) and an edge $A_2 \to A_1$ (due to the edge $v \to w$).

• Hmm ok I see what you're getting at. Still confused though. In this case the DAG represents a combinational boolean network where I guess $u$ would be the input node, $w$ would be the output node, and $v$ would be some logic gate. If you make the partition you describe, the circuit wouldn't have the same logic anymore (I don't even think it would be a combinational network anymore), which seems to defeat the whole purpose. It seems like that partition would be invalid from the get go b/c it changes the logic (essentially, the paths aren't preserved). Or maybe that's the whole point?
– jaip
Sep 8 '17 at 1:40
• @jaip, the question doesn't specify any restrictions on what partitions are "allowed", so I don't know how to answer that. I'm going by what is in the question, so if there is other context that is relevant, I might be missing it.
– D.W.
Sep 8 '17 at 2:10
• Ok fair enough. I was going off the problem formulation given in the linked paper. My guess is that might be why those partitions were noteworthy. Thanks for the example!
– jaip
Sep 8 '17 at 2:17