# A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
## 6 Discussion
The feature removal analysis indicated that three features--**variation**, **minimum degree** and **maximum degree**--all seem to be related in that removing all of them significantly reduces performance and performance increases as more of them are added, until all three are added, which does not provide a significant improvement in performance. Our interpretation is that there is a predictive signal that is present only in those three features but any two of them are sufficient to reproduce it. Besides this insight, feature removal provided little that we could interpret and that was not in direct conflict with other parts of the same analysis. The analysis of the Decision Tree model indicated that size, density and variability are the most important characteristics of a graph; however, those could be expressed through different numerical features. For instance, the first quartile of the degree distribution (**q1**), which could be an indicator for graph size or density, was by far the most predictive feature in our Decision Tree model. To make discussing this easier, we will separate the concepts _characteristic_ and _feature. Characteristics_ are a more general characteristic that can be represented by many different _features; features_ are specifically the numbers we described in Section 3.1. Combining the results from all three approaches is difficult, as they often conflict. However, the insight from the Decision Tree analysis that size, density and variability are the most important characteristics of a graph, no matter what specific numerical proxy they are represented by, is consistent with results from other analysis approaches. The feature removal analysis indicated that **variation**, **minimum degree** and **maximum degree** together carry an important signal--these features can be considered a proxy for size, density and variability. The impurity reduction results are also consistent with this, as they showed **variation**, **density** and **minimum degree** being the three most important features. The relative lack of importance stemming from which proxy is used for these characteristics of a graph is also demonstrated by **q1**--while that feature is by far the most important in the Decision Tree analysis, the other two analytical approaches did not show it being particularly important, as it was only seventh out of thirteen in impurity reduction and did not make even one appearance in the sets of important features that the feature removal analysis yielded. Our experiments also yield some insights into the strengths and weaknesses of the solvers. One insight that becomes clear from the class distribution in both our unfiltered dataset and the three filtered datasets (as per Section 4.2) is that the solver **tdlib** is dominant on 'easy' graphs. In the unfiltered dataset, **tdlib** was the best algorithm for 97% of graphs which became progressively less with a higher lower bound being imposed on difficulty. At the lower bound of 30 s (Dataset A), **tdlib** was the best algorithm for 77% of graphs; at 10 s (Dataset B) that number went further down to 45%; and at 30 s (Dataset C) it was only 38%. Notably, **tdlib** kept the \"most victories\" title in the unfiltered dataset, Dataset A and Dataset B; however, in Dataset C, **tamaki** dehroned it with 49% versus 38%. Undeniably, going from a 97% dominance to no longer being the best algorithm as difficulty increases tells us something about the strengths and weaknesses of the solver. This is also confirmed by our analysis of the Decision Tree model, which clearly showed **tdlib** had an aptitude for smaller and sparser graphs. Another insight is **tamaki**'s robustness. It is the best solver in terms of terminations **and** run time on all three datasets, despite not being the best in terms of victories on datasets A and B. Most interesting is **tamaki**'s time performance on Dataset A--while **tdlib** has more than four times as many victories on that dataset as **tamaki** does, **tamaki**'s run time is still about 30% better than **tdlib**'s.