id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
17893 Incorrect decomposition returned by Graph.treewidth ncohen "As reported on asksage [1], the function `Graph.treewidth` can return incorrect tree decompositions.
{{{
sage: graphs.PathGraph(10).treewidth(certificate=True).vertices()
[{2}, {1}, {4}, {8, 9}, {8}, {6}, {0}, {3}, {5}, {7}]
}}}
The computations are actually done right (the width returned is correct), but my attempts to ""simplify"" the tree while it is being built simplified.. a bit too much.
The way it is done now is a bit more correct, though a tad more ressource-consuming. Nothing important, as the post-processing is infiinitely cheaper than the actual solving anyway.
{{{
sage: graphs.PathGraph(10).treewidth(certificate=True).vertices()
[{0, 1}, {4, 5}, {1, 2}, {2, 3}, {8, 7}, {8, 9}, {6, 7}, {5, 6}, {3, 4}]
}}}
Nathann
[1] http://ask.sagemath.org/question/26011/treewidth/" defect closed major sage-6.6 graph theory fixed dcoudert slelievre Nathann Cohen Frédéric Chapoton N/A d3d967d4fddd903aaadeb3a809575eef815e1fde d3d967d4fddd903aaadeb3a809575eef815e1fde