Is it possible to achieve further acceleration of the calculation of the connectivity characteristics of a random graph?

The article discusses new methods for accelerating the calculation of some characteristics of the connectivity of a random graph (the probability of a subset of vertices being connected (all-terminal reliability, ATR), the average probability of pairwise connectivity (ARC), the mathematical expectation of the size of a connected subgraph containing a selected vertex (MENC), and some others). These problems have a proven non-polynomial complexity and, as a rule, approximate solutions are sought. However, with the development of computer technology and the development of parallel algorithms, finding exact solutions has become possible for graphs of a sufficiently large dimension to solve practical problems (up to hundreds of vertices in the case of a small average degree). In addition, the solutions to these problems found over the years, including various methods of reduction and decomposition by the author of the article [1-10], made it possible to further increase the dimension of the calculated graphs. Exact solutions are also needed to assess the quality of approximate algorithms. Most explored is the task of finding ATR and two-terminal reliability (pairwise connectivity, s - t connectivity), while various tasks may require and other characteristics of network’s reliability [11] and consider different constrains, graph diameter in particular [12]. Various techniques are proposed for developing the well-known factorization method, when instead of considering one resolving edge, a certain small subset of edges chosen in a special way is considered. It is shown how to use cut edges as such a subset, leading to the possibility of effective use of known decomposition formulas for cut of 1, 2 or 3-vertices [13].