Opened 6 years ago
Closed 6 years ago
#17893 closed defect (fixed)
Incorrect decomposition returned by Graph.treewidth
| Reported by: | ncohen | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | sage-6.6 |
| Component: | graph theory | Keywords: | |
| Cc: | dcoudert, slelievre | Merged in: | |
| Authors: | Nathann Cohen | Reviewers: | Frédéric Chapoton |
| Report Upstream: | N/A | Work issues: | |
| Branch: | d3d967d (Commits, GitHub, GitLab) | Commit: | d3d967d4fddd903aaadeb3a809575eef815e1fde |
| Dependencies: | Stopgaps: |
Status badges
Description (last modified by )
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
Change History (10)
comment:1 Changed 6 years ago by
- Branch set to u/ncohen/17893
- Commit set to 427e907433481b576b57769fc09949ac12e8765a
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Description modified (diff)
comment:3 follow-up: ↓ 5 Changed 6 years ago by
- Reviewers set to Frédéric Chapoton
- Status changed from needs_review to needs_work
3 failing doctests
comment:4 Changed 6 years ago by
- Commit changed from 427e907433481b576b57769fc09949ac12e8765a to d3d967d4fddd903aaadeb3a809575eef815e1fde
comment:5 in reply to: ↑ 3 Changed 6 years ago by
- Status changed from needs_work to needs_review
3 failing doctests
Sorry about that.
I just rebased the patch over the latest beta and added a commit to fix that.
It is a rather good news, by the way: it means that the decompositions are smaller than previously.
Nathann
comment:7 Changed 6 years ago by
Thaaaaaaaaanks for the review ;-)))
Nathann
P.S. : Do you have any ticket I could review ?
comment:8 Changed 6 years ago by
Well, #17901 should be very easy..
comment:9 Changed 6 years ago by
HMmmm... Well, I am already having a very hard time checking that q=A([1,2,3]) actually calls the .check function. Also, it seems that the AffinePermutationGroup group be a deprecated import, as we try to store them all in groups.affine.*. Anyway, first there is your patch to deal with ^^;
Nathann
comment:10 Changed 6 years ago by
- Branch changed from u/ncohen/17893 to d3d967d4fddd903aaadeb3a809575eef815e1fde
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
trac #17893: Incorrect decomposition returned by Graph.treewidth