Complexity Analysis of Triangular Decomposition over F_2 with Strongly Chordal Graphs
Zhaoxing Qi, Chenqi Mou · 2024
In this paper, we first introduce a new vertex order of graphs called the substrong elimination ordering based on maximal cliques of the graphs and prove that such an ordering can fully characterize strongly chordal graphs. By using this ordering we propose a new strategy for selecting polynomials for computation in algorithms for triangular decomposition over Math 1 . Then we show that when this ordering is used as the variable order for triangular decomposition of a polynomial set whose associated graph is strongly chordal, the variables of any polynomial occurring in the decomposition are contained in certain maximal cliques, which gives a uniform description of the structural changes in the decomposition when combined with a bounded treewidth. Consequently, we prove that for any input set of ℓ polynomials in n variables with a strongly chordal associated graph of treewidth m, the complexity for triangular decomposition over Math 2 with the proposed selection strategy is Math 3 , smaller than the original O(ℓn) when m ≪ n.