two errors in treewidth for non-connected graphs

[sagetrac-evandomme]

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

Firstly, if I run

  {{{#!python
  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

  {{{#!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

  {{{#!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).

Component: graph theory

Keywords: tree decomposition, tree-width

Author: Mélodie Lapointe, Élise Vandomme

Branch/Commit: cb3f492

Reviewer: David Coudert

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

[dcoudert]

comment:1

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.

[sagetrac-mlapointe]

Branch: u/mlapointe/two_erros_in_treewidth_for_non_connected_graphs

[sagetrac-mlapointe]

New commits:

7ea89b8

trac 23546: Correcting the errors in treewidth

[sagetrac-mlapointe]

Commit: 7ea89b8

[dcoudert]

comment:4

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.

[videlec]

comment:5

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

[dcoudert]

comment:6

I have corrected the ticket title.

[dcoudert]

Reviewer: David Coudert

[sagetrac-git]

Changed commit from 7ea89b8 to fc21663