Graph.treewidth is slow and sometimes produces invalid tree decompositions

[Ordoviz]

Problem Description

Graph.treewidth(algorithm='tdlib') uses an outdated algorithm from the treedec library (formerly known as tdlib), which sometimes produces invalid tree decompositions (see Additional Information). A faster algorithm is available.

Proposed Solution

Update a single line

-    treedec::exact_decomposition_cutset(G, T, lb);
+    treedec::exact_decomposition_ex17(G, T, lb);

in

sage/src/sage/graphs/graph_decompositions/sage_tdlib.cpp

Line 71 in 842f12b

treedec::exact_decomposition_cutset(G, T, lb);

to switch to the (much faster!) algorithm that won the PACE 2017 treewidth challenge.

This requires that the header-only gala library is installed and the C macro HAVE_GALA_GRAPH_H is defined when Sage is built. Distros that package Sage with tdlib support would need to update their Sage packages.

Also, the debug messages printed by exact_decomposition_ex17 should be patched out.

Alternatives Considered

Switching to another library for computing exact tree decompositions (but treedec still appears to be the best).

Additional Information

Example graphs for which exact_decomposition_cutset produces invalid tree decompositions (and exact_decomposition_ex17 works correctly):

from sage.graphs.graph_decompositions.tree_decomposition import is_valid_tree_decomposition
for g6 in ['HQhVv]~', 'J~~~~|_gM@_', 'K~~~~|Og@`wE', 'K~~~~{oSD@wE', 'K~~~~z{WD?wB']:
    G = Graph(g6)
    T = G.treewidth(certificate=True)
    print(is_valid_tree_decomposition(G, T))

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

[dcoudert]

Some errors have already been reported in #39404 and freetdi/tdlib#49.
The source code of treedec has moved from https://github.com/freetdi/tdlib to https://codeberg.org/freetdi/treedec
It remains to do some work on both side...