wrong treewidth calculated with tdlib

[Ordoviz]

Steps To Reproduce

No response

Expected Behavior

sage: g=Graph('J??s[`HS@O_')
sage: g.treewidth(algorithm='tdlib')
3
sage: g.treewidth(algorithm='sage')
3

This graph has treewidth 3 according to HoG.

Actual Behavior

sage: g=Graph('J??s[`HS@O_')
sage: g.treewidth(algorithm='tdlib')
4
sage: g.treewidth(algorithm='sage')
3

Additional Information

@felix-salfelder This issue is similar to #38159. The graph J??s[`HS@O_ is given in .gr format below:

p tw 11 15
1 7
1 8
2 9
2 10
3 6
3 11
4 6
4 8
4 10
5 7
5 9
5 11
6 7
8 9
10 11

Environment

• OS: Arch Linux with treedec 0.9.3 (I also tried tdlib 0.9.3+ built from source, no difference)
• Sage Version: 10.5 (I also tried 10.6.beta5 via sagemath-git, no difference)

Checklist

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

[Ordoviz]

I found the smallest graph for which g.treewidth(algorithm='tdlib') != g.treewidth(algorithm='sage'). It has 10 vertices:

sage: g=Graph('I@?LShgTG')
sage: g.treewidth(algorithm='tdlib')
4
sage: g.treewidth(algorithm='sage')
3

p tw 10 15
1 7
1 8
2 9
2 10
3 4
3 7
3 9
4 8
4 10
5 6
5 7
5 9
6 8
6 10
9 10

[felix-salfelder]

Thank you, very useful. Definitely a bug, possibly to do with preprocessing. I tried

$ ./tdecomp --ex17 < sage_bug_39404.gr > ex17.td
$ ./tdecomp --ta < sage_bug_39404.gr > ta.td
$ grep ^s ta.td ex17.td
ta.td:s td 7 4 10
ex17.td:s td 7 5 10  <= !!
$ td-validate sage_bug_39404.gr ta.td 
valid
$ td-validate sage_bug_39404.gr ex17.td 
valid

iirc ex17 == pp+ta, but I need more time to debug.

[dcoudert]

I usedthe following got to get all biconnected graphs (option -C) graphs of order 10 for which tdlib is returning a wrong result. We can turn these graphs to .gr format if you need. After some time, I get some warnings from treedec. Don't know if it is useful.

sage: for g in graphs.nauty_geng(f"10 -C"):
....:     if g.treewidth(algorithm='tdlib') != g.treewidth(algorithm='sage'):
....:         print(g.graph6_string())
....: 
I?`FE_w\?
I?`FEaw\?
I?`Df@W\?
I?`Df?sf?
I?`Df?[L?
I?`Df@su?
I?`Db_kU?
I?`Db_kF?
I?`Dbbgt?
incomplete /Users/dcoudert/sage/local/include/treedec/exact_cutset.hpp:603:q_explore_cutsets
incomplete /Users/dcoudert/sage/local/include/treedec/exact_cutset.hpp:603:q_explore_cutsets
incomplete /Users/dcoudert/sage/local/include/treedec/exact_cutset.hpp:603:q_explore_cutsets
...