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.

  • $\begingroup$ 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! $\endgroup$ – D.W. Sep 7 '17 at 22:26
  • $\begingroup$ 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! $\endgroup$ – jaip Sep 8 '17 at 1:31
  • $\begingroup$ 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). $\endgroup$ – 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$).

  • $\begingroup$ 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? $\endgroup$ – jaip Sep 8 '17 at 1:40
  • $\begingroup$ @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. $\endgroup$ – D.W. Sep 8 '17 at 2:10
  • $\begingroup$ 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! $\endgroup$ – jaip Sep 8 '17 at 2:17

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.