On the Decomposition of Circuits into Minimally Interconnected Subcircuits

A. V. Korniyenko

(Presented by the scientific seminar of the Department of Automated Control Systems)

A problem that often arises in the layout of digital devices is considered: the decomposition of a circuit into mutually nonintersecting subcircuits satisfying a certain minimum criterion for the number of connections between them. Similar questions have previously been considered both by exact methods [1] and on the basis of heuristic principles [2]. In the present article the approach of [3] is developed, based on the concept of a minimal (strongly connected) group of elements. In particular, the conditions for minimality of groups are investigated, the concept of a quasi-minimal group is introduced, and, on the basis of the results obtained, an economical algorithm is proposed for finding all minimal groups of a circuit.

Basic concepts and formulation of the problem

To a circuit \(V\), constructed from functional elements and connections between them, there corresponds a graph \(\Gamma\) [4], in which two sets of vertices are distinguished: \(E\) and \(C\). Vertices from \(E\) correspond to functional elements, and vertices from \(C\) to electrical connections of the circuit. A vertex \(c_i \in C\) is joined by edges to the vertices \(e_j, e_k, \ldots, e_m\) \((e_q \in E,\ q=j,k,\ldots,m)\), if the \(i\)-th electrical connection links the functional elements \(j,k,\ldots,m\) with one another.

For convenience in the subsequent exposition, we shall agree to call vertices from the set \(E\) of the graph \(\Gamma\) elements, and those from the set \(C\) connections. Elements in the graph will be denoted by circles, and connections by points. We shall also denote by \(E(c_i)\) the set of elements adjacent to the connection \(c_i\), and by \(C(e_j)\) the set of connections adjacent to the element \(e_j\).

Definition 1. A connection \(c_i \in C\) is called, for a set \(B \subset E\) of elements,

— internal, if \(E(c_i)\cap B=E(c_i)\);

— boundary (or a terminal), if \(E(c_i)\cap B\ne E(c_i)\);

— external, if \(E(c_i)\cap B=\varnothing\).

Definition 2*. A subgraph \(R\subset\Gamma\), defined by a set \(B\subset E\) of elements and a set \(C(B)\) of connections, is called a group.

Since the choice of \(B\) uniquely determines \(R\), henceforth, for convenience, we shall call any set \(B\subset E\) of elements, sub-

the subgraph defined by this set. For a group \(H\) consisting of \(n\) pairwise disjoint groups \(\left(H=\bigcup_{k=1}^{n} B_k,\; B_i\cap B_j=\varnothing\ \text{for } i\ne j\right)\), the number of its terminals is determined [3] by the formula

\[ h=\sum_{i=1}^{n}\alpha(B_i)+\sum_{i,j=1}^{n}\alpha(B_i,B_j)+\sum_{i,j,k=1}^{n}\alpha(B_i,B_j,B_k)+\ldots \]
\[ \ldots+\sigma(B_i,B_j,\ldots,B_n). \tag{1} \]

In (1), \(\sigma(B_i,B_j,\ldots,B_m)\) denotes the number of boundary connections adjacent to the set of groups \(B_i,B_j,\ldots,B_m\). The number of internal connections adjacent to this set is denoted by \(\beta(B_i,B_j,\ldots,B_m)\). An example illustrating the application of formula (1) is given in Fig. 1.

\[ \begin{gathered} \alpha(\ell_1)=0,\quad \alpha(\ell_2)=1,\quad \alpha(\ell_3)=1;\\ \alpha(\ell_1,\ell_2)=0,\quad \alpha(\ell_1,\ell_3)=0,\quad \alpha(\ell_2,\ell_3)=1;\\ \alpha(\ell_1,\ell_2,\ell_3)=1;\\ \beta(\ell_1,\ell_2)=2,\quad \beta(\ell_1,\ell_3)=1,\quad \beta(\ell_2,\ell_3)=0;\\ \beta(\ell_1,\ell_2,\ell_3)=1. \end{gathered} \]

Fig. 1. Example of the application of formula (1)

Definition 3*. A group \(B\) is called minimal if, for any subgroup \(H\subset B\), the number of its terminals satisfies the inequality

\[ h>b. \tag{2} \]

Individual elements are regarded as minimal groups.

Theorem 1. [3]. Let \(K\) and \(L\) be minimal groups, with \(K\not\subset L\) and \(L\not\subset K\). Then \(K\) and \(L\) must be disjoint, i.e. \(K\cap L=\varnothing\).

Nevertheless, one minimal group may be contained entirely in another. For example, in Fig. 4 the groups \(K=\{e_1,e_2\}\) and \(L=\{e_1,e_2,e_3,e_4,e_5\}\) are minimal, with \(K\subset L\).

The property of minimal groups formulated in Theorem 1 is of primary interest from the standpoint of packaging. Indeed, sets of elements placed during packaging into different structural units of the same rank cannot intersect; however, these sets may be contained completely one in another if they are placed in structural units of different ranks. In addition, a minimal group, when placed wholly in a structural unit, ensures a minimal number of terminals. However, the algorithm proposed in [3] for finding minimal groups is not sufficiently efficient, since it relies mainly on enumeration. Thus the problem is to develop an algorithm suitable for investigating circuits with a number of elements large enough to be of practical interest.

Some additional properties of minimal groups

It is often impossible, in the graphs of circuits of digital devices, to isolate minimal groups because of the presence of a large number of boundary connections—

* The meaning of Definitions 2 and 3 is borrowed from [3].

for the graph as a whole. To remove this obstacle, we shall transform the original graph into a graph without boundary connections in the following way:

a) each boundary connection \(c_i\), adjacent to the elements \(e_j, e_k, \ldots, e_m\), is replaced (removing, for this purpose, the external edges incident to \(c_i\)) by an internal connection adjacent to the same elements;

b) each boundary connection adjacent to only one element is removed together with all edges incident to it.

Theorem 2. A group \(B\) that is minimal in the original graph \(\Gamma\) remains minimal also in the graph \(\Gamma^*\) without boundary connections obtained from \(\Gamma\) by the indicated transformation.

Proof. In \(B\), choose an arbitrary subgroup \(H \subset B\). Since \(B\) is a minimal group, \(h>b\) (by Definition 3). Let \(b^\circ\) and \(h^\circ\) be, respectively, that part of the terminals of the group \(B\) and the subgroup \(H\) which is lost when the graph \(\Gamma\) is transformed into \(\Gamma^*\). Since \(H \subset B\), we have \(b^\circ \geq h^\circ\), and hence \(h^*>b^*\), where \(b^*=(b-b^\circ)\) and \(h^*=(h-h^\circ)\) are the numbers of terminals, respectively, of the group \(B\) and the subgroup \(H\) in the graph \(\Gamma^*\). By the arbitrariness of the choice of \(H\), the assertion is valid for all subgroups of the group \(B\), which is what was required to prove the theorem. It is clear that the minimality of a group in the graph \(\Gamma^*\) does not necessarily imply its minimality in the graph \(\Gamma\).

Theorem 3. If the graph \(\Gamma\) is connected, then the graph \(\Gamma^*\) obtained from it without boundary connections is a minimal group.

Proof. It is clear that the transformation of the graph \(\Gamma\) into \(\Gamma^*\) does not destroy its connectedness. Therefore the number of terminals of any of its subgroups is not equal to zero. And since the number of terminals of the graph \(\Gamma^*\) is zero, the conditions required by Definition 3 for the minimality of \(\Gamma^*\) are thereby satisfied.

If the graph is not connected, then each of its components can be studied separately. Therefore the theorems proved make it possible, in what follows, to consider only connected graphs without boundary connections.

We shall say that a group \(B\) is an \(n\)-group if the number of elements entering it is equal to \(n\). As follows from Definition 3, in order to verify the minimality of an \(n\)-group, it is necessary to check that inequality (2) holds for all \(2^n-1\) of its subgroups. Therefore Theorem 4 is of special interest.

Theorem 4. Let \(B\) be an \(n\)-group containing no minimal \(m\)-subgroups, \(n>m>1\). Then, for \(B\) to be minimal, it is necessary and sufficient that, for any element \(K \subseteq B\), the inequality

\[ k>b, \tag{3} \]

hold.

Proof. The necessity of (3) follows from Definition 3. To prove the sufficiency of (3), suppose that the group satisfies all the conditions of Theorem 4 but is not minimal. Then, by Definition 3, in the group \(B\) there is a subgroup \(H \subset B\) such that \(h \leq b\). By the conditions of Theorem 4, \(H\) is also not minimal, and for this reason in \(H\) there is a subgroup \(F \subset H\) such that \(f \leq h\). Continuing in this way and taking into account that the group \(B\) consists of a finite number \(n\) of elements, we finally obtain a subgroup \(K\) consisting of one element and such that \(k \leq \cdots \leq f \leq h \leq b\), i.e., \(k \leq b\). However, this contradicts the conditions of Theorem 4, which is what was required to establish for its proof.

Thus, if it is always ensured that the \(n\)-group under study contains no minimal \(m\)-subgroups, \(n>m>1\), then verification of its minimality can be performed in \(n\) steps instead of \(2^n-1\). We shall say that a group \(F\) is subjected to contraction [4] if all its internal-

connection are omitted together with the edges incident to them, and all elements of the group \(F\) are identified. Then the process of finding minimal groups satisfying the conditions of Theorem 4 can be carried out as follows.

1. If the graph contains exactly one element, go to item 7.
2. Set \(n=2\).
3. Form all possible \(n\)-groups.
4. Using (3), check the minimality of all \(n\)-groups. If a group is minimal, write out its composition and contract it.
5. If minimal groups have been found, go to item 1.
6. Increase \(n\) by one and go to item 3.
7. End.

The possibility of applying this process rests on the meaning of Theorem 1 and a number of its corollaries, considered in detail in [3]. However, the weak point in this algorithm is item 3. The point is that the number of different \(n\)-groups that can be formed in a graph of \(N\) elements is equal to the number \(\binom{N}{n}\) of combinations of \(N\) elements taken \(n\) at a time, whereas the number of minimal \(n\)-groups in such a graph cannot exceed (Theorem 1) the integer part of the number \(N/n\). Hence the necessity of restricting the enumeration when carrying out item 3 is obvious. The first step in this direction is provided by Theorem 5.

Theorem 5. For the minimality of a group \(B\) it is necessary and sufficient that, for any subgroup \(K \subset B\) and its complement \(L=B/K\), the inequalities

\[ \begin{aligned} \beta(K,L)&>\alpha(L),\\ \beta(K,L)&>\alpha(K). \end{aligned} \tag{4} \]

hold.

Proof. From Definition 3 it follows that for \(K\) and \(L\) the inequalities

\[ \begin{aligned} k&>b,\\ l&>b. \end{aligned} \tag{5} \]

must hold.

By formula (1) we find (Fig. 2):

\[ \begin{aligned} b&=\alpha(K)+\alpha(K,L)+\alpha(L),\\ k&=\alpha(K)+\alpha(K,L)+\beta(K,L),\\ l&=\alpha(L)+\alpha(K,L)+\beta(K,L). \end{aligned} \tag{6} \]

Substituting (6) into (5) and simplifying, we obtain the required system of inequalities (4).

Corollary 1. For the minimality of a group \(B\) it is necessary that, for any subgroup \(K \subset B\) and its complement \(L=B\), the inequality

\[ \beta(K,L)>0. \tag{7} \]

hold.

Fig. 2. To Theorem 5

Inequality (7) is obtained from (4) if we set \(\alpha(K)=\alpha(L)=0\).

Let us call groups satisfying the conditions of Corollary 1 \(\beta\)-connected. Indeed, it is not especially difficult to show that in such a group any two elements can be connected by a chain passing only through internal connections. Since a minimal \(n\)-group must necessarily be \(\beta\)-connected, for its formation one can use an algorithm analogous to the algorithm [4] for testing the connectedness of a graph.

1. At the first step, assign to the \(n\)-group being formed the element with the minimal number of terminals \(k^{\circ}\) (the expediency of this will become clear from what follows).

2. Let \(K\) be the set of elements already assigned to the \(n\)-group and constituting a \(\beta\)-connected subgroup. If \(n(K)<n\), \(n(K)=|K|\), then the set \(K\) can be \(\beta\)-connectedly extended. For this it is sufficient to choose any of the connections that are boundary connections for \(K\) and assign to the group being formed all elements adjacent to it. It is obvious that the group extended in this way will also be \(\beta\)-connected.

However, although this method of forming an \(n\)-group limits the enumeration, it does not use all the properties of minimal groups. Indeed, at the \(i\)-th step the set \(C_i(K)\) of connections that are boundary connections for \(K\) is divided into subsets: \(C_i^{\alpha}(K)\)—connections left at the \(i\)-th step among the boundary connections, and \(C_i^{\beta}(K)\)—connections assigned at the \(i\)-th step to the internal connections of the \(n\)-group being formed. Let \(r_i=|C_i^{\alpha}(K)|\) be the number of terminals of the \(n\)-group being formed at the \(i\)-th step. Then it is obvious that the inequality

\[ b \ge r_i . \tag{8} \]

must hold.

Since the \(n\)-group being formed must be minimal, the inequality \(k^{\circ}>b\) must hold; hence, taking (8) into account, we obtain

\[ k^{\circ}>r_i . \tag{9} \]

Thus, when at the \(i\)-th step \(C_i(K)\) is divided into \(C_i^{\alpha}(K)\) and \(C_i^{\beta}(K)\), condition (9) must be satisfied. An additional restriction is imposed by Theorem 6.

Theorem 6. For the optimality of the described process of forming an \(n\)-group, it is necessary that at each step \(i\) the condition
\[ C_{i-1}^{\alpha}(K)\subset C_i^{\alpha}(K) \]
be satisfied.

Proof. Suppose that at step \(i\), \(C_{i-1}^{\alpha}(K)\not\subset C_i^{\alpha}(K)\). But this then means that \(C_{i-1}^{\alpha}(K)\cap C_i^{\beta}(K)\ne\varnothing\), since \(C_i(K)=C_i^{\alpha}(K)\cup C_i^{\beta}(K)\). Consequently, part of the connections assigned to the internal ones at the \(i\)-th step could have been assigned to them already at the \((i-1)\)-th step, which proves the theorem.

Corollary 2. For the optimal process of forming a group, the quantity \(r_i\) is a nonincreasing function of \(i\), \(i=1,2,\ldots,m\), where \(m\) is the number of the step at which formation ends. Obviously.

At step \(m\), when \(|K|=n\), \(C_m^{\alpha}(K)\) must be equal to \(C_m(K)\), since further extension of the group is impossible. If it should turn out that inequality (9) is also satisfied at the \(m\)-th step, then the resulting \(n\)-group (by virtue of Theorem 4) is minimal, since the first element assigned to this group has the minimal number of terminals \(k^{\circ}\).

Quasi-minimal groups

In the algorithm considered in the preceding section, the process of searching for minimal groups can be accelerated still further if groups that are not minimal are contracted. The basic property that such a group must possess is that it cannot partially intersect minimal groups. Groups having this property are quasi-minimal groups.

Definition 3′. A group \(B\) is called quasi-minimal if, for any subgroup \(H \subset B\), the number of its terminals satisfies the inequality

\[ h \geqslant b, \]

Theorem 1′. Let \(B\) be a minimal group, and \(S\) a quasi-minimal group. Moreover, \(B \not\subset S\) and \(S \not\subset B\). Then the groups \(B\) and \(S\) must be disjoint, i.e. \(B \cap S = \varnothing\).

Proof. Let \(B \cap S = F\), \(B = K \cup F\), and \(S = L \cup F\) (Fig. 3). From Definitions 3 and 3′ and the conditions of Theorem 1′ it follows that, for \(F \ne \varnothing\), the inequalities must hold:

\[ \begin{aligned} k &> b,\\ l &\geqslant s. \end{aligned} \tag{10} \]

Using formula (1), we obtain for (10) the following equivalent system of inequalities:

\[ \begin{aligned} \beta(K,F) &> \alpha(F)+\alpha(L,F)+\beta(L,F),\\ \beta(L,F) &\geqslant \alpha(F)+\alpha(K,F)+\beta(K,F). \end{aligned} \tag{11} \]

Fig. 3. For Theorem 1

These inequalities, when \(F \ne \varnothing\), are jointly inconsistent. Only by assuming that \(F=\varnothing\) (in which case \(B=K\), \(S=L\); the inequalities in (10) are replaced by equalities; all \(\alpha\) and \(\beta\) in (11) that contain \(F\) are set equal to zero) do we obtain a jointly solvable system of equations. This proves the theorem.

For quasi-minimal groups, theorems analogous to Theorems 4 and 5 for minimal groups are also valid. Their proof is entirely analogous to the proofs of the corresponding theorems for minimal groups and therefore is not given here.

Theorem 4′. Let \(B\) be an \(n\)-group containing no quasi-minimal \(m\)-subgroups, \(n>m>1\). Then, for the quasi-minimality of \(B\), it is necessary and sufficient that for every element \(K \in B\) the inequality

\[ k \geqslant b, \tag{3′} \]

be satisfied.

Theorem 5′. For the quasi-minimality of a group \(B\), it is necessary and sufficient that, for every subgroup \(K \subset B\) and its complement \(L = B/K\), the inequalities

\[ \begin{aligned} \beta(K,L) &\geqslant \alpha(L),\\ \beta(K,L) &\geqslant \alpha(K). \end{aligned} \tag{4′} \]

be satisfied.

Corollary 1′. For the quasi-minimality of a group \(B\), it is necessary that, for any subgroups \(K \subset B\) and \(L = B/K\), the inequality

\[ \beta(K,L) \geqslant 0. \]

be satisfied.

As is evident, a quasi-minimal group need not be \(\beta\)-connected. However, since we are interested primarily in minimal groups, among quasi-minimal groups only \(\beta\)-connected ones will be considered henceforth.

Algorithm

Summarizing the results obtained in the preceding sections, we formulate a procedure for finding minimal groups in a graph without boundary connections.

1. If the graph contains exactly one element, go to item 11.

2. By examining the connections of the graph, find the connection with the minimum number of elements adjacent to it,

\[ \gamma^\circ=\min_i |E(c_i)|. \]

1. Set \(n=\gamma^\circ\).

2. Mark all connections having a number of adjacent elements \(\gamma>n\) as boundary connections for the \(n\)-group being formed.

3. Among the elements having unmarked (nonboundary) adjacent connections, choose an element with the minimum number of adjacent connections,

\[ k^\circ=\min_j |C(e_j)|, \]

and assign it to the set \(K\) of elements of the \(n\)-group being formed. If no such element is found, then remove all marks and go to item 9.

Fig. 4. Example of decomposing a graph into minimal groups

1. Form a \(\beta\)-connected \(n\)-group satisfying, at each step \(i\), the condition

\[ k^\circ \ge r_i \quad (i=1,2,\ldots,m). \]

If such a group cannot be formed, go to item 8.

1. Write down the composition of the minimal or quasi-minimal group found; assign to it the next number in order, not coinciding with the numbers of the elements and of the previously found groups; contract the found \(n\)-group; mark as boundary all connections adjacent to the elements that entered the \(n\)-group. After this go to item 5.

2. Mark as boundary all connections adjacent to the element with number of terminals \(k^\circ\) that was assigned first to the \(n\)-group being formed; after this go to item 5.

3. If in item 6 minimal or quasi-minimal groups were found, then go to item 1.

4. Increase \(n\) by one and go to item 4.

5. End.

Figure 4 gives an example borrowed from [3]. In the graph, thick lines show the edges excluded from consideration as boundary connections. Minimal groups are outlined with solid lines, and quasi-minimal ones with dashed lines. It is not difficult to establish that, in order to find 6 minimal groups of the graph, 18 groups must be analyzed. To find the same groups by means of the algorithm of [3], it is necessary to analyze, in the best case, 26 groups and, in the worst case, 62 groups (depending on the order in which they are formed).

Conclusion

A more efficient method for finding minimal groups of a graph has been proposed and justified. The increase in efficiency is obtained mainly through the use of previously unknown properties of minimal groups to limit exhaustive search and to reduce the size of the problem more rapidly in the course of its solution, as a result of contracting not only minimal groups but also quasiminimal groups introduced into consideration.

The efficiency of the algorithm depends substantially on the degree of completeness of the graph; this, however, is not a drawback, since the graphs of digital-device circuits are, as a rule, very far from complete.

References

1. L. L. Gorinshtein. On cutting graphs. Izv. AN SSSR, “Technical Cybernetics,” 1969, No. 1.

2. Kernighan B. W. and Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. 49, No. 2 (Feb. 1970), 291—307.

3. Luccio F. Sami Mariagiovanna. On the decomposition of networks in minimally interconnected subnetworks. “IEEE Trans. Circuit Theory,” 1969, 16, No. 2, 184—188.

4. Berge. Graph Theory and Its Applications. Moscow, IL, 1962.