#17893: Incorrect decomposition returned by Graph.treewidth
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.6
defect | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 427e907433481b576b57769fc09949ac12e8765a
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17893 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> As reported on asksage [1], the function `Graph.treewidth` can return
> incorrect tree decompositions.
>
> 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.
>
> Nathann
>
> [1] http://ask.sagemath.org/question/26011/treewidth/
New description:
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/
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17893#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
