Ask Your Question
0

treewidth()

asked 2015-03-02 19:41:25 -0500

storm gravatar image

updated 2015-03-04 08:37:26 -0500

Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property?

To illustrate with a concrete example (not the one above):

M = Matrix([[0, 0, 1, 0, 1],
            [0, 0, 1, 0, 0],
            [1, 1, 0, 1, 0],
            [0, 0, 1, 0, 0],
            [1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()

This returns:

[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]

Clearly (0,2) is an edge of the original graph but the answer above does not have a bag that contains both 0 and 2.

edit retag flag offensive close merge delete

Comments

Give us the tree please.

Nathann gravatar imageNathann ( 2015-03-03 05:49:10 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2015-03-04 10:33:49 -0500

Nathann gravatar image

updated 2015-03-04 10:35:10 -0500

Here it is ! This is now ticket #17893. There was a problem indeed, but not in the actual computations. I was trying to simplify the final tree too much, and well. To the point that some things that had their importance actually vanished :-P

It is updated. Very very slightly more time-consuming, but a clearer code. Good deal.

By the way it is in 'needs_review', i.e. somebody (anybody) needs to double check it before it makes it into Sage.

[1] http://trac.sagemath.org/ticket/17893

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-03-02 19:41:25 -0500

Seen: 232 times

Last updated: Mar 04 '15