Opened 4 years ago

Closed 4 years ago

# two errors in treewidth for non-connected graphs

Reported by: Owned by: evandomme minor sage-8.1 graph theory tree decomposition; tree-width Mélodie Lapointe, Élise Vandomme David Coudert N/A cb3f492 cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3

### Description

The function treewidth() with the option certificate=True encounters two problems on non-connected graphs.

Firstly, if I run

g=Graph({0:[1,2], 3:[4,5], 4:[5]})
g.treewidth(certificate=True)

I obtain

which contradicts the fact that the tree-width of the graph is 2.

The problem comes from the part ".edges(labels=False)" in

# 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

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).

### comment:1 Changed 4 years ago by dcoudert

You are right and this is what we get when using tdlib (optional package)

sage: g = Graph({0:[1,2], 3:[4,5], 4:[5]})
sage: T = g.treewidth(algorithm='tdlib', certificate=True)
sage: print T.edges(labels=0)
[({3, 4, 5}, {0, 2}), ({0, 2}, {0, 1})]

Are you planing to write the patch ? If so I can review it.

### comment:2 Changed 4 years ago by mlapointe

• Branch set to u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs

### comment:3 Changed 4 years ago by mlapointe

• Commit set to 7ea89b8684b7bc1727387f35856944056fa790e3
• Status changed from new to needs_review

New commits:

 ​7ea89b8 trac 23546: Correcting the errors in treewidth

### comment:4 Changed 4 years ago by dcoudert

The patch is working well. However, a few minor changes are needed.

• :trac:`23546`:: -> The decomposition is a tree (:trac:`23546`)::. This will improve the documentation.
• You must add an empty line after between the line with :trac:`23546` and the line sage: g = Graph({0:[1,2], 3:[4,5]}).
• sage: vertices = set({}) -> sage: vertices = {}.
• v = T[0].vertices()[0] -> v = next(T[0].vertex_iterator()). There is no need for first building the list of vertices. We can use the iterator to get the first vertex.
• tree.add_edge([t.vertices()[0],v]) -> tree.add_edge(t.vertices()[0], v). Here also, there is no need for creating a list.

Thank you.

### comment:5 Changed 4 years ago by vdelecroix

But... what is an erros!? ;-)

### comment:6 Changed 4 years ago by dcoudert

• Reviewers set to David Coudert
• Summary changed from two erros in treewidth for non-connected graphs to two errors in treewidth for non-connected graphs

I have corrected the ticket title.

### comment:7 Changed 4 years ago by git

• Commit changed from 7ea89b8684b7bc1727387f35856944056fa790e3 to fc216636b3553e54e9b7ce3b89e2feae7bcc609b

Branch pushed to git repo; I updated commit sha1. New commits:

 ​fc21663 trac: 23546 implementing minors changing suggested by dcoubert.

### comment:8 Changed 4 years ago by mlapointe

I have implemented all the suggestion except this one:

sage: vertices = set({}) -> sage: vertices = {}

since the object {} is a dictionary and I want to have an empty set.

### comment:9 follow-up: ↓ 11 Changed 4 years ago by dcoudert

In the example, the last test assumes an ordering of the vertices. This is not a good idea (actually, ticket #22349 proposes to remove the sorting).

sage: [1,2,3,4] == [4,3,2,1]
False

sage: for s in t.vertices():
....:    vertices.update(s)
sage: vertices == set(g.vertices())
True

### comment:10 Changed 4 years ago by git

• Commit changed from fc216636b3553e54e9b7ce3b89e2feae7bcc609b to cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3

Branch pushed to git repo; I updated commit sha1. New commits:

 ​cb3f492 trac 23546: Remove the assumption on the other of vertices in the test.

### comment:11 in reply to: ↑ 9 Changed 4 years ago by mlapointe

In the example, the last test assumes an ordering of the vertices. This is not a good idea (actually, ticket #22349 proposes to remove the sorting).

sage: [1,2,3,4] == [4,3,2,1]
False

sage: for s in t.vertices():
....:    vertices.update(s)
sage: vertices == set(g.vertices())
True

I agree and I have made the modification.

### comment:12 Changed 4 years ago by dcoudert

• Status changed from needs_review to positive_review

For me this patch is now good to go. Thank you.

### comment:13 Changed 4 years ago by vbraun

• Branch changed from u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs to cb3f49228771d74ca8f6e448a1f9e1cdea7bb4a3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.