Graph expression complexities and simultaneous linear recurrences

Abstract

The paper investigates relationships between algebraic expressions and graphs. Using the decomposition method we generate special simultaneous systems of linear recurrences for sizes of graph expressions. We propose techniques which provide closed-form solutions for these systems.

Introduction

We consider a labeled two-terminal directed acyclic graph (st-dag in [1]) that has only one source and only one sink in which each edge has a unique label. An algebraic expression is a graph expression (a factoring of a graph [1]) if it is algebraically equivalent to the sum of edge label products corresponding to all possible paths between the source and the sink of the graph. We de ne the total number of labels in an algebraic expression as the complexity of the algebraic expression. Expressions with a minimum (or, at least, a polynomial) complexity may be considered as a key to generating efficient algorithms on distributed systems.

A series-parallel graph is de ned recursively so that a single edge is a seriesparallel graph and a graph obtained by a parallel or a series composition of series-parallel graphs is series-parallel [1]. A series-parallel graph expression has a representation in which each label appears only once [1]. Generating an optimum factored form for non-series-parallel graph expressions is a highly complex problem. Interrelations between graphs and expressions are discussed in [1], [4], [5] and other works.

We generate expressions of a number of non-series-parallel graphs using the decomposition method. This method is based on revealing subgraphs of approximately equal sizes in the initial graph. The resulting polynomial-size expression is produced by a special composition of subexpressions describing these subgraphs. In many cases, computing of complexity of the obtained expression is reduced to solving a simultaneous system of three linear recurrences. In this paper we propose a method which provides a closed-form (explicit) solution for this system.

The decomposition method

Consider a graph called a full square rhomboid (F SR) [4]. We split every nontrivial graph through two decomposition vertices (number 4 in Fig. 1) which are chosen in the middle of the upper and the lower groups of the graph. Any path from vertex 1 to vertex 7 in Fig. 1 passes either through one of decomposition vertices or through edge b4. Thus the graph is decomposed into six subgraphs two of which are F SR (connected by b4 in Fig. 1) and four ones are called single-leaf full square rhomboids (F SR1). Each F SR1 is decomposed into six new subgraphs in the similar way (Fig. 2(a)). They are one F SR, three F SR1 and two dipterous full square rhomboids (F SR2). Decomposition of possible varieties of F SR2 (see the example in Fig. 2(b)) gives two F SR1 and four F SR2 subgraphs.

e1 -6r

c6 -7r

6 (b) 8 T (m) = 2T (m )+ 4T1 (m )+ 1 < T1 (m) = T (m2 )+ 3T1 (m2 )+ 2T2 (m2 )+ 1 : T2 (m) = 2T1 2(m2 )+ 4T2 2(m2 )+ 1 , ( 1 ) where T1(m) and T2(m) are the total numbers of labels in expressions of F SR1 and F SR2, respectively, of size m and T ( 1 ) = 0, T1 ( 1 ) = 1, T2 ( 1 ) = 3.

One can see that the sum of the coefficients in each of three simultaneous recurrences ( 1 ) equals 6 and T1 (m) = 21 T (m) + 12 T2 (m). Therefore, system ( 1 ) may be presented in general terms as a following simultaneous system of three linear nonhomogeneous recurrences of rst order [6] with constant coefficients: 8 an = <

bn = : cn = 11an 1 + 21an 1 + 31an 1 + 12bn 1 + 22bn 1 + 32bn 1 + 13cn 1 + 23cn 1 + 33cn 1 + In this system 11 + 12 + 13 = 21 + 22 + 23 = 31 + 32 + 33 and a sequence bn is a linear combination of sequences an and cn (a0, b0, and c0 are initial values of a, b, and c, respectively).

Our research indicates that system ( 2 ) appears in solving a problem of deriving the explicit form of graph expression complexity for various graphs of regular structure. Some of subgraphs emerged in the result of decomposition are exactly of the same structure as the initial one. Others are supplemented at one end by elements which were in the middle of the split graph. The structure of these onesided subgraphs does not change in the middle and, hence, they are decomposed in the same way. This gives, together with the subgraphs of the initial structure and one-sided subgraphs, two-sided subgraphs supplemented at both ends by the elements of the inner structure. The two-sided subgraphs are decomposed likewise and their splitting yields new one-sided and two-sided subgraphs.

The coefficients in ( 2 ) equal the numbers of their respective subgraphs. Since subgraphs of all types are decomposed into the same numbers of new subgraphs, the sums of coefficients in all recurrences of ( 2 ) are equal. It is logical that a characteristic of a graph supplemented by one set of additional elements is a weighted average of characteristics of graphs, one of which has no additional elements and another one has two sets. Speci cally, we proved that the weights are equal if the sizes of all revealed subgraphs are equal and the number of subgraphs with a given kind of end adjacent to the location of the split from the left is equal to the number of subgraphs of the same kind of end adjacent to the location of the split from the right (see system ( 1 )).

Therefore, solving system ( 2 ) being a rather special problem for a discrete mathematics as a whole, is a common problem from the perspective of the algorithmic theory.

It is possible to divide ( 2 ) into separate recurrences using the HamiltonCayley theorem [2] and further to attempt to use general methods for linear recurrences solving [6] (methods of characteristic equations (roots), of generating functions, etc.). However, using the results obtained in [3], we propose a simpler way that accommodates the restrictions imposed on the coefficients and the unknowns of system ( 2 ) and directly gives a closed form for its solution. 3

Results

Lemma 1. If 21 )

21)n + + where a0 and b0 are initial values of a and b, respectively. whwwe21re 31 1′+1 =33w1a1nd21fo+r al2l2t,hes1′e2 p=airs wwo21f si2m1u+ltan23e,ous2′1rec=urwr1e1nc3e1s +

Theorem 1. Given system ( 2 ) and the following conditions: 1. 11 + 12 + 13 = 21 + 22 + 23 = 31 + 32 + 33, 2. 9 real constants w1; w2, w1 + w2 = 1, that 8 n, bn = w1an + w2cn, 11

C1 C1

C1 (C1)n

C1 1 + where C1 = 11+ 12+ 13 (C1 ̸= 1), C2 = 12+ w12 13, C3 = 11 ww21 23 (C3 ̸= 1), C4 = 12 + w12 13 + 21 ww12 23 (C4 ̸= 0), C5 = and a0, b0, c0 are initial values of a, b, c, respectively. 21

21+

Conclusions and open problems

We have proposed a method that gives a closed-form solution for a special simultaneous system of three linear recurrences. Sums of coefficients in the recurrences are equal, and each recurrent variable is a linear combination of two other recurrent variables. The solution is applied to deriving explicit forms of graph expression complexities. Speci cally, using this method, we have obtained the following formula for the number of labels in expressions of full square rhomboids of size m (m = 2p): 4859 mlog2 6 290 mlog2 3 51 . Our intent is to determine the class of graphs for which the complexities of their expressions go hand in hand with these recurrences.

We are going to generalize this method to a system of an arbitrary (or, at least, a larger) number of recurrences and, nally, to develop a method capable to handle simultaneous recurrences with equal sums of coefficients in columns.

References

1. Bein , W.W. , Kamburowski , J. , Stallmann , M.F.M. : Optimal Reduction of TwoTerminal Directed Acyclic Graphs . SIAM Journal of Computing 21 ( 6 ), 1112 { 1129 ( 1992 )

2. Bloom , D. M. : Linear Algebra and Geometry . Cambridge University Press, Cambridge, London ( 1979 )

3. Korenblit , M. : Efficient Computations on Networks, Ph.D. Thesis , Bar-Ilan University, Israel ( 2004 )

4. Korenblit , M. : Decomposition Methods for Generating Algebraic Expressions of Full Square Rhomboids and Other Graphs . Discrete Applied Mathematics 228 , 60 - 72 ( 2017 )

5. Mintz , A. , Golumbic , M.C. : Factoring Boolean Functions Using Graph Partitioning . Discrete Applied Mathematics 149 ( 1-3 ), 131 - 153 ( 2005 )

6. Rosen , K.H. (ed.): Handbook of Discrete and Combinatorial Mathematics . CRC Press, Chapman & Hall/CRC, Boca Raton, second edition ( 2010 )