# A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
## 1 Introduction  
### The Importance of Treewidth  
The _treewidth_ of an undirected graph \(G=(V,E)\), denoted \(tw(G)\), is a measure of how \"treelike\" it is [1]. Trees have treewidth 1 and the treewidth of a graph can be as large as \(|V|-1\). The concept of treewidth is closely linked to that of a _tree decomposition_ of \(G\), which is the arrangement of a set of subsets of \(V\) into a tree backbone, such that certain formal criteria are satisfied; these are described in the preliminaries. The width of the tree decomposition is equal to the size of its largest subset, minus 1 and \(tw(G)\) is the minimum width, ranging over all possible tree decompositions of \(G\)[2]. In recent decades treewidth has attracted an immense amount of attention, due to the observation that many NP-hard problems on graphs become polynomial-time solveable on graphs of bounded treewidth. This is because, when a tree decomposition of width \(t\) is available, it is usually possible to organise dynamic programming algorithms in a hierarchical way such that the intermediate lookup-tables consulted by the dynamic programming, have size that is bounded by a function of \(t\)[3]. In fact, because of this many NP-hard problems on graphs can actually be solved in time \(f(tw(G))\cdot\mathrm{poly}(n)\), where \(n=|V(G)|\) and \(f\) is a computable (typically exponential) function that depends only on \(tw(G)\)We say then that the problem is _fixed parameter tractable_ (FPT) with respect to \(tw(G)\). For this reason, treewidth has become a cornerstone of the parameterized complexity literature, which advocates a more fine-grained approach to running time complexity than the traditional approach of expressing worst-case running times purely as a function of the size of the input [4]. Given its relevance as a 'gateway to tractability', treewidth has attracted enormous interest not just from the combinatorial optimisation and theoretical computer science communities but also from many other domains such as artificial intelligence (particularly Bayesian inference and constraint satisfaction: see Reference [5] for a highly comprehensive list), computational biology [6] and operations research [7]. Unfortunately, computing the treewidth (equivalently, a minimum-width tree decomposition) is NP-hard [8]. This does not nullify its usefulness, however. Alongside practical heuristics (see e.g., References [9; 10]) there is an extensive literature on computing the treewidth of a graph exactly, in spite of its NP-hardness. Some of these results have a purely theoretical flavour, most famously in Reference [11] but there has also been a consistent stream of research on computing treewidth exactly _in practice_. Such practical algorithms have an interesting history. Until a few years ago, progress had been somewhat incremental; see References [12; 13] for representative articles from this period. However, in 2016 the Parameterized Algorithms and Computational Experiments (PACE) treewidth challenge, an initiative of the parameterized complexity community to promote the development of practically efficient algorithms, stimulated a major breakthrough. The _positive-instance driven_ dynamic programming approach pioneered by [PERSON] [14] allowed the treewidth to be computed exactly for many graphs that had hitherto been considered out of range [14; 15]. This 2017 edition of PACE subsequently yielded an additional hundred-fold speed-up over PACE 2016 results [16]. Following the advances triggered by PACE 2016 and [PERSON]'s approach, there are now a number of highly advanced exact treewidth solvers, several of which we will encounter later in this article. When studying these solvers we observed that, once the solving time rose above a few seconds, no single solver universally dominated over (i.e., ran more quickly than) all the others.