  Let tw(G) denote the treewidth of graph G. Given a graph G and a positive
integer k such that tw(G) <= k + 1, we are to decide if tw(G) <= k. We give a
certifying algorithm RTW ("R" for recursive) for this task: it returns one or
more tree-decompositions of G of width <= k if the answer is YES and a minimal
contraction H of G such that tw(H) > k otherwise.
  RTW uses a heuristic variant of Tamaki's PID algorithm for treewidth
(ESA2017), which we call HPID. RTW, given G and k, interleaves the execution of
HPID with recursive calls on G /e for edges e of G, where G / e denotes the
graph obtained from G by contracting edge e. If we find that tw(G / e) > k,
then we have tw(G) > k with the same certificate. If we find that tw(G / e) <=
k, we "uncontract" the bags of the certifying tree-decompositions of G / e into
bags of G and feed them to HPID to help progress. If the question is not
resolved after the recursive calls are made for all edges, we finish HPID in an
exhaustive mode. If it turns out that tw(G) > k, then G is a certificate for
tw(G') > k for every G' of which G is a contraction, because we have found tw(G
/ e) <= k for every edge e of G. This final round of HPID guarantees the
correctness of the algorithm, while its practical efficiency derives from our
methods of "uncontracting" bags of tree-decompositions of G / e to useful bags
of G, as well as of exploiting those bags in HPID.
  Experiments show that our algorithm drastically extends the scope of
practically solvable instances. In particular, when applied to the 100
instances in the PACE 2017 bonus set, the number of instances solved by our
implementation on a typical laptop, with the timeout of 100, 1000, and 10000
seconds per instance, are 72, 92, and 98 respectively, while these numbers are
11, 38, and 68 for Tamaki's PID solver and 65, 82, and 85 for his new solver
(SEA 2022).
