Strongly and transitive chordal graphs and their applications in complexity analysis of triangular decomposition

Triangular decomposition is a versatile computational tool for studying polynomial ideals, but the complexity is not well understood due to its intricate behaviors. Inspired by the recent interplay between polynomial system solving and chordal graphs, in this paper we analyze the complexity of triangular decomposition by using chordal graphs. We first introduce a new vertex ordering of graphs called the substrong elimination one which characterizes strongly chordal graphs. Using this ordering, we propose a polynomial selection strategy for triangular decomposition over F₂ and show that for polynomial sets with strongly chordal associated graphs, the variables of any polynomial occurring in the decomposition with this strategy are contained in certain maximal clique. For ℓ polynomials in n variables with such an associated graph of treewidth m, under certain worst-case assumptions, the complexity of triangular decomposition over F₂ using this strategy is proved to be [Formula presented], smaller than the original O(ℓⁿ) when m≪n. To extend these results to other algorithms for triangular decomposition over any field, we introduce the concept of transitive chordal graph based on the transitive vertex ordering. Then when the transitive perfect elimination ordering is used for a collection of algorithms, the similar inclusion of the variables in the maximal cliques is proved without requiring additional selection strategies. As a direct consequence, these algorithms are chordality-preserving when combined with transitive chordal graphs. At the end, we provide complexity analyses for two algorithms using transitive chordal graphs of bounded treewidths.