Opened 4 years ago

Closed 4 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) Commit: d3d967d4fddd903aaadeb3a809575eef815e1fde
Dependencies: Stopgaps:

Description (last modified by 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/

Change History (10)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/17893
  • Commit set to 427e907433481b576b57769fc09949ac12e8765a
  • Status changed from new to needs_review

New commits:

427e907trac #17893: Incorrect decomposition returned by Graph.treewidth

comment:2 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:3 follow-up: Changed 4 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to needs_work

3 failing doctests

comment:4 Changed 4 years ago by git

  • Commit changed from 427e907433481b576b57769fc09949ac12e8765a to d3d967d4fddd903aaadeb3a809575eef815e1fde

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b8464cbtrac #17893: Incorrect decomposition returned by Graph.treewidth
d3d967dtrac #17893: Broken doctests

comment:5 in reply to: ↑ 3 Changed 4 years ago by ncohen

  • 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:6 Changed 4 years ago by chapoton

  • Status changed from needs_review to positive_review

ok, thanks.

comment:7 Changed 4 years ago by ncohen

Thaaaaaaaaanks for the review ;-)))

Nathann

P.S. : Do you have any ticket I could review ?

comment:8 Changed 4 years ago by chapoton

Well, #17901 should be very easy..

comment:9 Changed 4 years ago by ncohen

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 4 years ago by vbraun

  • Branch changed from u/ncohen/17893 to d3d967d4fddd903aaadeb3a809575eef815e1fde
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.