Wrong result with tdlib for treewidth

[dcoudert]

Steps To Reproduce

sage: from sage.graphs.graph_decompositions.tree_decomposition import width_of_tree_decomposition
sage: G = Graph('q~~|~q{mLhUo}?v?EO`{?h`?wo@w?fo?As_?lG?Cp_?Uc??{?_?|???Y_G?@gH??{?_?A{???Dp???Dk???Ax????l????Dh????Qo???GkG???_lG????Q_???I@p?G???uO????As????@@gH????FG??A??AW_??A??d????CG@w?C????PE?@????D@G?C???t?O??????')
sage: G.treewidth(algorithm='sage')
5
sage: G.treewidth(algorithm='tdlib')
6
sage: T = G.treewidth(algorithm='tdlib', certificate=True)
sage: width_of_tree_decomposition(G, T)
6

Expected Behavior

sage: G.treewidth(algorithm='tdlib')
5

Actual Behavior

sage: G.treewidth(algorithm='tdlib')
6

Additional Information

No response

Environment

- **OS**: macOS 12.7.5 and fedora 39
- **Sage Version**: 10.4.beta8

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

[dcoudert]

Another example with only 10 nodes

sage: G = Graph('I~~}vPlr_')
sage: G.treewidth(algorithm='sage')
5
sage: G.treewidth(algorithm='tdlib')
6

[dimpase]

@felix-salfelder

[felix-salfelder]

I'm not familiar with the compressed string representation. Please remind me how to convert 'I~~}vPlr_' into a graph.

Which version of tdlib (aka treedec) is this, and which algorithm does it use?

Thanks

[mkoeppe]

See also:

• try to upgrade tdlib #30813

[felix-salfelder]

I figured that 'I~~}vPlr_' has 10 vertices and 32 edges.

It looks like this in gr format

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

With this input, tdecomp --ex17 (develop branch) gives me

s td 9 6 10
b 1 1 5
b 2 1 2 5
b 3 1 2 5 7
b 4 1 2 4 5 7
b 5 1 2 4 5 7 10
b 6 1 2 4 5 6 10
b 7 1 2 3 4 5 6
b 8 1 2 3 5 8
b 9 2 3 5 6 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 9

Similar decompositions also from fi, ppfi and bmd (all with tw 5, if tw is the size of a biggest bag minus 1).

I can't say much about the cython sage integration, and obviously the results may depend on vertex order and such things. Do you actually get a suboptimal decomposition? Which one?

[dcoudert]

The graph has 10 vertices and 33 edges

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

and we get the decomposition:

s td 4 7 10
b 1 1 2 5 6 7 10
b 2 1 2 3 4 5 6 7
b 3 1 2 3 5 6 8
b 4 2 3 5 6 8 9
1 2
2 3
3 4

We clearly have to use a newer version of tdlib. We currently call a former function sage_exact_decomposition from version 0.3.1.p0. We will have to figure out how to use the current interfaces.

[felix-salfelder]

On Thu, Jun 06, 2024 at 11:33:16PM -0700, David Coudert wrote: The graph has 10 vertices and 33 edges

Thanks, interesting. I used a tool "showg" to decode the string. Then hand edited the output... It had to go wrong. The current algorithms also work on the 33 edge graph, but I havent tried the dated exact decomposition (cutset I suppose), as it's not enabled in tdecomp.

We clearly have to use a newer version of tdlib. We currently call a former function `sage_exact_decomposition` from version `0.3.1.p0`. We will have to figure out how to use the current interfaces.

The new python bindings need work. Perhaps it should be split out, and become more "pythonic", with a dependency on libtreedec provided by the main package. Time will tell, suggestions welcome.

[dimpase]

On Thu, Jun 06, 2024 at 11:33:16PM -0700, David Coudert wrote:

The graph has 10 vertices and 33 edges

Thanks, interesting. I used a tool "showg" to decode the string. Then
hand edited the output... It had to go wrong.

The current algorithms also work on the 33 edge graph, but I havent
tried the dated exact decomposition (cutset I suppose), as it's not
enabled in tdecomp.

We clearly have to use a newer version of tdlib. We currently call a
former function sage_exact_decomposition from version 0.3.1.p0. We
will have to figure out how to use the current interfaces.

The new python bindings need work. Perhaps it should be split out, and
become more "pythonic", with a dependency on libtreedec provided by the
main package. Time will tell, suggestions welcome.

The best would be to have a Python package on PyPI, dependent on libtreedec. Then it would become the only point of entry to tdlib in Sage, simplifying things.

[felix-salfelder]

On Fri, Jun 07, 2024 at 05:09:40AM -0700, Dima Pasechnik wrote: The best would be to have a Python package on PyPI, dependent on libtreedec. Then it would become the only point of entry to tdlib in Sage, simplifying things.

If I understand correctly, we should eventually build a shared library. A starting point could be the various treedec/_*.cpp minus the BOOST_PYTHON_MODULE wrapper code. Apparently, these steps are needed. - copy treedec to lib - remove all references to python in lib/* - adjust rules in lib/*, link it all into libtreedec.so - do the opposite in treedec/*, link with -ltreedec - (examples/treedec: also use libtreedec) - .. whatever else to meet PyPI needs. All we need is a volunteer, but count me in as a reviewer.

[mkoeppe]

We clearly have to use a newer version of tdlib.

• build/pkgs/tdlib: Update to 0.9.3 #38163