{'fraction_non_alphanumeric': 0.021949078138718173, 'fraction_numerical': 0.000877963125548727, 'mean_word_length': 4.858611825192802, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Calculation of typical running time of a branch-and-bound algorithm for the vertex-cover problem

The vertex-cover problem is one of a collection of NP-complete problems studied actively in the science community. The problem’s solving time is in the worst case exponential, but the running time varies for different vertex-cover realizations. From experimental data, different phases can be identified for the running time and the analysis of vertex-cover algorithms back the observed results up. Interestingly the worst-case typical average solutions are located at the xc(c) phase boundary, which is studied analytically in the book [2] and in the paper [3]. This summary is based on these two documents. We start by giving a short description of the vertex-cover problem and introducing symbols related to the problem. We proceed and introduce a branch-and-bound algorithm for finding vertex covers of a given size for a graph. Experimental results are displayed in order to show the running time landscape we are dealing with. The experimental results show different phases, which can be studied analytically further. The vertex-cover algorithm’s traversal of the configuration tree is explained. The relationship between different kinds of configuration tree traversals and the phases shown in the experimental results is described. The analysis of the vertex-cover algorithm is started by introducing the first-moment method. The method provides us with a lower bound for the xc(c) phase boundary for large c values. It also shows a general way of using the average as a bound that can be exploited in similar situations. We start the analysis of the typical running time by examining the behaviour of the algorithm during the first descent into the configuration tree. This produces results that can be used to find the nodes in the configuration tree, where a solution is unrecoverable and a subtree must be backtracked. In the backtracking analysis the typical running time for the largest subtree is approximated. This yields an analytical solution for the typical running time in the backtracking phase. The analytical results are compared to the experimental results presented before. As the last step in this paper, a summary of the most important results is given.