Estimation of Expressions’ Complexities for Two-Terminal Directed Acyclic Graphs

The paper investigates relationship between algebraic expressions and graphs. Our intention is to simplify graph expressions and eventually find their shortest representations. We prove the decomposition lemma which asserts that the shortest expression of a subgraph of a graph G is not larger than the shortest expression of G. Using this finding, we estimate an upper bound of a size of the shortest expression for any two-terminal directed acyclic graph.