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,,