Incorrect decomposition returned by Graph.treewidth

[nathanncohen]

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/

CC: @dcoudert @slel

Component: graph theory

Author: Nathann Cohen

Branch/Commit: d3d967d

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/17893

[nathanncohen]

Commit: 427e907

[nathanncohen]

New commits:

427e907

trac #17893: Incorrect decomposition returned by Graph.treewidth

[nathanncohen]

Branch: u/ncohen/17893

[fchapoton]

comment:3

3 failing doctests

[fchapoton]

Reviewer: Frédéric Chapoton

[sagetrac-git]

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

b8464cb	trac #17893: Incorrect decomposition returned by Graph.treewidth
d3d967d	trac #17893: Broken doctests

[sagetrac-git]

Changed commit from 427e907 to d3d967d

[nathanncohen]

comment:5

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

[fchapoton]

comment:6

ok, thanks.

[nathanncohen]

comment:7

Thaaaaaaaaanks for the review ;-)))

Nathann

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

[fchapoton]

comment:8

Well, #17901 should be very easy..

[nathanncohen]

comment:9

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

[vbraun]

Changed branch from u/ncohen/17893 to d3d967d