# A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
## 4 Experiments and Results
### Experimental Setup
The reasoning behind this approach is that if algorithms' run times lie outside of the defined _moderate_ area, there is little gains to be made with algorithm selection anyway. If a graph is too easy, a comparatively weak algorithm can still solve it quickly; if a graph is too hard, there simply is no \"correct\" algorithm to select. Formally, if \(lb\) is the lower bound, \(ub\) is the allotted time (upper bound) and \(rt(A,G)\) is the run time of algorithm \(A\) on graph \(G\), then if \((\forall A:lb\geq rt(A,G))\vee(\forall A:ub\leq rt(A,G))\) holds, \(G\) will be excluded. Three different lower bounds were used--1, 10 and 30 s--and graphs that passed the conditions were stored in datasets A, B and C, respectively. (For the upper bound, we used the time-out limit of 30 min). This necessitates us making a distinction between _source_ datasets and _filtered_ datasets--the source datasets are those publicly available datasets that we started with; the filtered datasets are the sum of all graphs from all source datasets which passed through the respective filter. Table 1 breaks down how many graphs from each source dataset remained in each filtered dataset. The same label-assigning procedure described above was repeated. The resulting class distributions are shown in Table 2. Afterwards, Random Forest models were trained using the Python machine-learning package _scikit-learn_[48], using all default settings except for allowing for up to 1000 trees in the forest. Both Leave-One-Out (LOO) cross-validation and 5-fold cross-validation were used in order to decrease the importance of randomness in the train-test split. 5-fold cross validation was repeated 100 times with different random seeds for the same purpose; at the end, the results from all 100 runs were averaged. These two cross-validation methods produced virtually identical results, hence we only present the results for LOO cross-validation. The results presented are for the entire dataset. Our algorithm selector is evaluated based on its predictions for each graph when it was in the test set--that is, a model is never evaluated on a graph that it has been trained on. We deemed the usage of a hold-out set unnecessary, as no hyper-parameter optimisation took place. (For readers not familiar with these technical machine learning terms, we refer to survey literature such as [PERSON] et al. [49]). \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Datasets** & **Unfiltered** & **A** & **B** & **C** \\ \hline bonus & 100 & 36 & 36 & 35 \\ cfg & 1797 & 43 & 1 & 0 \\ ex & 200 & 200 & 172 & 137 \\ he & 200 & 26 & 17 & 17 \\ named & 150 & 47 & 14 & 11 \\ pace2016 & 145 & 95 & 16 & 13 \\ toto & 27,123 & 594 & 92 & 53 \\ transit & 19 & 10 & 4 & 4 \\ uai & 133 & 27 & 14 & 43 \\ vc & 178 & 58 & 42 & 38 \\ vcPACE & 100 & 6 & 6 & 6 \\ dimacsMC & 80 & 20 & 13 & 10 \\ sat\_sr15 & 115 & 0 & 0 & 0 \\ Total & 30,340 & 1162 & 427 & 337 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The total number of graphs per source dataset and the number of those graphs in filtered datasets A, B and C (see Sections 4.1 and 4.2 for clarification). \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Unfiltered** & **Dataset A** & **Dataset B** & **Dataset C** \\ \hline Jdrasil & 55 & 55 & 49 & 42 \\ tamaki & 209 & 209 & 186 & 168 \\ tdlib & 29,234 & 898 & 192 & 127 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Number of graphs, within each dataset, for which the given algorithm was fastest (see Sections 4.1 and 4.2). An additional model was trained on Dataset B, using a single CART decision tree as a classifier and 50% of the data as a training set. The purpose of this model was not to optimise predictive performance but interpretability, as a Decision Tree model is significantly easier to interpret than a Random Forest model. We hoped that this interpretation would provide insight into what makes solvers good on some instances and bad on others. Dataset B was chosen due to having the best class distribution, with no clearly best algorithm.