id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
23546 two errors in treewidth for non-connected graphs evandomme "The function treewidth() with the option certificate=True encounters two problems on non-connected graphs.
Firstly, if I run
{{{
#!div style=""font-size: 80%""
{{{#!python
g=Graph({0:[1,2], 3:[4,5], 4:[5]})
g.treewidth(certificate=True)
}}}
}}}
I obtain [[br]]
[[Image(http://lacim.uqam.ca/~elise.vandomme/treewidth.png)]] [[br]]
which contradicts the fact that the tree-width of the graph is 2.
The problem comes from the part "".edges(labels=False)"" in
{{{
#!div style=""font-size: 80%""
{{{#!python
# Disconnected cases
if not g.is_connected():
if certificate is False:
if k is None:
return max(cc.treewidth() for cc in g.connected_components_subgraphs())
else:
return all(cc.treewidth(k) for cc in g.connected_components_subgraphs())
else:
return Graph(sum([cc.treewidth(certificate=True).edges(labels=False)
for cc in g.connected_components_subgraphs()],[]),
name=""Tree decomposition"")
}}}
}}}
Indeed, one of the connected components has a tree decomposition that consists of a single vertex. So its list of edges is an empty list and we lose information when we just consider the concatenation of edges list.
Secondly, a tree decomposition is a tree by definition. But when I run
{{{
#!div style=""font-size: 80%""
{{{#!python
g=Graph({0:[1,2], 3:[4,5]})
g.treewidth(certificate=True)
}}}
}}}
the result is two non-connected edges. This minor problem can be corrected by adding an arbitrary edge between the i-th and i+1-th connected components of the result (for all possible i)." defect closed minor sage-8.1 graph theory fixed tree decomposition; tree-width Mélodie Lapointe, Élise Vandomme David Coudert N/A cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3 cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3