Tree decompositions#
This module implements tree-decomposition methods.
A tree-decomposition of a graph \(G = (V, E)\) is a pair \((X, T)\), where \(X=\{X_1, X_2, \ldots, X_t\}\) is a family of subsets of \(V\), usually called bags, and \(T\) is a tree of order \(t\) whose nodes are the subsets \(X_i\) satisfying the following properties:
The union of all sets \(X_i\) equals \(V\). That is, each vertex of the graph \(G\) is associated with at least one tree node.
For every edge \((v, w)\) in the graph, there is a subset \(X_i\) that contains both \(v\) and \(w\). That is, each edge of the graph \(G\) appears in a tree node.
The nodes associated with vertex \(v \in V\) form a connected subtree of \(T\). That is, if \(X_i\) and \(X_j\) both contain a vertex \(v \in V\), then all nodes \(X_k\) of the tree in the (unique) path between \(X_i\) and \(X_j\) contain \(v\) as well, and we have \(X_i \cap X_j \subseteq X_k\).
The width of a tree decomposition is the size of the largest set \(X_i\) minus one, i.e., \(\max_{X_i \in X} |X_i| - 1\), and the treewidth \(tw(G)\) of a graph \(G\) is the minimum width among all possible tree decompositions of \(G\). Observe that, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.
The length of a tree decomposition, as proposed in [DG2006], is the maximum diameter in \(G\) of its bags, where the diameter of a bag \(X_i\) is the largest distance in \(G\) between the vertices in \(X_i\) (i.e., \(\max_{u, v \in X_i} dist_G(u, v)\)). The treelength \(tl(G)\) of a graph \(G\) is the minimum length among all possible tree decompositions of \(G\).
While deciding whether a graph has treelength 1 can be done in linear time (equivalent to deciding if the graph is chordal), deciding if it has treelength at most \(k\) for any fixed constant \(k \leq 2\) is NP-complete [Lokshtanov2009].
Treewidth and treelength are different measures of tree-likeness. In particular, trees have treewidth and treelength 1:
sage: T = graphs.RandomTree(20)
sage: T.treewidth()
1
sage: T.treelength()
1
The treewidth of a cycle is 2 and its treelength is \(\lceil n/3 \rceil\):
sage: [graphs.CycleGraph(n).treewidth() for n in range(3, 11)]
[2, 2, 2, 2, 2, 2, 2, 2]
sage: [graphs.CycleGraph(n).treelength() for n in range(3, 11)]
[1, 2, 2, 2, 3, 3, 3, 4]
The treewidth of a clique is \(n-1\) and its treelength is 1:
sage: [graphs.CompleteGraph(n).treewidth() for n in range(3, 11)]
[2, 3, 4, 5, 6, 7, 8, 9]
sage: [graphs.CompleteGraph(n).treelength() for n in range(3, 11)]
[1, 1, 1, 1, 1, 1, 1, 1]
This module contains the following methods
Compute the treewidth of \(G\) (and provide a decomposition). |
|
Compute the treelength of \(G\) (and provide a decomposition). |
|
Check whether \(T\) is a valid tree-decomposition for \(G\). |
|
Return a reduced tree-decomposition of \(T\). |
|
Return the width of the tree decomposition \(T\) of \(G\). |
Methods#
- class sage.graphs.graph_decompositions.tree_decomposition.TreelengthConnected#
Bases:
object
Compute the treelength of a connected graph (and provide a decomposition).
This class implements an algorithm for computing the treelength of a connected graph that virtually explores the graph of all pairs
(vertex_cut, connected_component)
, wherevertex_cut
is a vertex cut of the graph of length \(\leq k\), andconnected_component
is a connected component of the graph induced byG - vertex_cut
.We deduce that the pair
(vertex_cut, connected_component)
is feasible with treelength \(k\) ifconnected_component
is empty, or if a vertexv
fromvertex_cut
can be replaced with a vertex fromconnected_component
, such that the pair(vertex_cut + v, connected_component - v)
is feasible.INPUT:
G
– a sage Graphk
– integer (default:None
); indicates the length to be considered. When \(k\) is an integer, the method checks that the graph has treelength \(\leq k\). If \(k\) isNone
(default), the method computes the optimal treelength.certificate
– boolean (default:False
); whether to also compute the tree-decomposition itself
OUTPUT:
TreelengthConnected(G)
returns the treelength of \(G\). When \(k\) is specified, it returnsFalse
when no tree-decomposition of length \(\leq k\) exists orTrue
otherwise. Whencertificate=True
, the tree-decomposition is also returned.EXAMPLES:
A clique has treelength 1:
sage: from sage.graphs.graph_decompositions.tree_decomposition import TreelengthConnected sage: TreelengthConnected(graphs.CompleteGraph(3)).get_length() 1 sage: TC = TreelengthConnected(graphs.CompleteGraph(4), certificate=True) sage: TC.get_length() 1 sage: TC.get_tree_decomposition() Tree decomposition of Complete graph: Graph on 1 vertex
A cycle has treelength \(\lceil n/3 \rceil\):
sage: TreelengthConnected(graphs.CycleGraph(6)).get_length() 2 sage: TreelengthConnected(graphs.CycleGraph(7)).get_length() 3 sage: TreelengthConnected(graphs.CycleGraph(7), k=3).is_less_than_k() True sage: TreelengthConnected(graphs.CycleGraph(7), k=2).is_less_than_k() False
- get_length()#
Return the length of the tree decomposition.
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import TreelengthConnected sage: G = graphs.CycleGraph(4) sage: TreelengthConnected(G).get_length() 2 sage: TreelengthConnected(G, k=2).get_length() 2 sage: TreelengthConnected(G, k=1).get_length() Traceback (most recent call last): ... ValueError: no tree decomposition with length <= 1 was found
- get_tree_decomposition()#
Return the tree-decomposition.
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import TreelengthConnected sage: G = graphs.CycleGraph(4) sage: TreelengthConnected(G, certificate=True).get_tree_decomposition() Tree decomposition of Cycle graph: Graph on 2 vertices sage: G.diameter() 2 sage: TreelengthConnected(G, k=2, certificate=True).get_tree_decomposition() Tree decomposition of Cycle graph: Graph on 1 vertex sage: TreelengthConnected(G, k=1, certificate=True).get_tree_decomposition() Traceback (most recent call last): ... ValueError: no tree decomposition with length <= 1 was found
- is_less_than_k()#
Return whether a tree decomposition with length at most \(k\) was found.
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import TreelengthConnected sage: G = graphs.CycleGraph(4) sage: TreelengthConnected(G, k=1).is_less_than_k() False sage: TreelengthConnected(G, k=2).is_less_than_k() True sage: TreelengthConnected(G).is_less_than_k() Traceback (most recent call last): ... ValueError: parameter 'k' has not been specified
- sage.graphs.graph_decompositions.tree_decomposition.is_valid_tree_decomposition(G, T)#
Check whether \(T\) is a valid tree-decomposition for \(G\).
INPUT:
G
– a sage GraphT
– a tree decomposition, i.e., a tree whose vertices are the bags (subsets of vertices) of the decomposition
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import is_valid_tree_decomposition sage: K = graphs.CompleteGraph(4) sage: T = Graph() sage: T.add_vertex(Set(K)) sage: is_valid_tree_decomposition(K, T) True sage: G = graphs.RandomGNP(10, .2) sage: T = G.treewidth(certificate=True) sage: is_valid_tree_decomposition(G, T) True
The union of the bags is the set of vertices of \(G\):
sage: G = graphs.PathGraph(4) sage: T = G.treewidth(certificate=True) sage: _ = G.add_vertex() sage: is_valid_tree_decomposition(G, T) False
Each edge of \(G\) is contained in a bag:
sage: G = graphs.PathGraph(4) sage: T = G.treewidth(certificate=True) sage: G.add_edge(0, 3) sage: is_valid_tree_decomposition(G, T) False
The bags containing a vertex \(v\) form a subtree of \(T\):
sage: G = graphs.PathGraph(4) sage: X1, X2, X3 = Set([0, 1]), Set([1, 2]), Set([2, 3]) sage: T = Graph([(X1, X3), (X3, X2)]) sage: is_valid_tree_decomposition(G, T) False
- sage.graphs.graph_decompositions.tree_decomposition.reduced_tree_decomposition(T)#
Return a reduced tree-decomposition of \(T\).
We merge all edges between two sets \(S\) and \(S'\) where \(S\) is a subset of \(S'\). To do so, we use a simple union-find data structure to record merge operations and the good sets.
Warning
This method assumes that the vertices of the input tree \(T\) are hashable and have attribute
issuperset
, e.g.,frozenset
orSet_object_enumerated
.INPUT:
T
– a tree-decomposition
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import reduced_tree_decomposition sage: from sage.graphs.graph_decompositions.tree_decomposition import is_valid_tree_decomposition sage: G = graphs.PathGraph(3) sage: T = Graph() sage: T.add_path([Set([0]), Set([0, 1]), Set([1]), Set([1, 2]), Set([2])]) sage: T.order() 5 sage: is_valid_tree_decomposition(G, T) True sage: T2 = reduced_tree_decomposition(T) sage: is_valid_tree_decomposition(G, T2) True sage: T2.order() 2
- sage.graphs.graph_decompositions.tree_decomposition.treelength(G, k=None, certificate=False)#
Compute the treelength of \(G\) (and provide a decomposition).
The length of a tree decomposition, as proposed in [DG2006], is the maximum diameter in \(G\) of its bags, where the diameter of a bag \(X_i\) is the largest distance in \(G\) between the vertices in \(X_i\) (i.e., \(\max_{u, v \in X_i} dist_G(u, v)\)). The treelength \(tl(G)\) of a graph \(G\) is the minimum length among all possible tree decompositions of \(G\). See the documentation of the
tree_decomposition
module for more details.INPUT:
G
– a sage Graphk
– integer (default:None
); indicates the length to be considered. When \(k\) is an integer, the method checks that the graph has treelength \(\leq k\). If \(k\) isNone
(default), the method computes the optimal treelength.certificate
– boolean (default:False
); whether to also return the tree-decomposition itself
OUTPUT:
G.treelength()
returns the treelength of \(G\). When \(k\) is specified, it returnsFalse
when no tree-decomposition of length \(\leq k\) exists orTrue
otherwise. Whencertificate=True
, the tree-decomposition is also returned.ALGORITHM:
This method virtually explores the graph of all pairs
(vertex_cut, connected_component)
, wherevertex_cut
is a vertex cut of the graph of length \(\leq k\), andconnected_component
is a connected component of the graph induced byG - vertex_cut
.We deduce that the pair
(vertex_cut, connected_component)
is feasible with treelength \(k\) ifconnected_component
is empty, or if a vertexv
fromvertex_cut
can be replaced with a vertex fromconnected_component
, such that the pair(vertex_cut + v, connected_component - v)
is feasible.In practice, this method decomposes the graph by its clique minimal separators into atoms, computes the treelength of each of atom and returns the maximum value over all the atoms. Indeed, we have that \(tl(G) = \max_{X \in A} tl(G[X])\) where \(A\) is the set of atoms of the decomposition by clique separators of \(G\). When
certificate == True
, the tree-decompositions of the atoms are connected to each others by adding edges with respect to the clique separators.See also
treewidth()
computes the treewidth of a graph.path_decomposition()
computes the pathwidth of a graph.module
vertex_separation
.
EXAMPLES:
The PetersenGraph has treelength 2:
sage: G = graphs.PetersenGraph() sage: G.treelength() 2
Disconnected graphs have infinite treelength:
sage: G = Graph(2) sage: G.treelength() +Infinity sage: G.treelength(k=+Infinity) True sage: G.treelength(k=2) False sage: G.treelength(certificate=True) Traceback (most recent call last): ... ValueError: the tree decomposition of a disconnected graph is not defined
Chordal graphs have treelength 1:
sage: G = graphs.RandomChordalGraph(30) sage: while not G.is_connected(): ....: G = graphs.RandomChordalGraph(30) sage: G.treelength() 1
Cycles have treelength \(\lceil n/3 \rceil\):
sage: [graphs.CycleGraph(n).treelength() for n in range(3, 11)] [1, 2, 2, 2, 3, 3, 3, 4]
- sage.graphs.graph_decompositions.tree_decomposition.treelength_lowerbound(G)#
Return a lower bound on the treelength of \(G\).
See [DG2006] for more details.
INPUT:
G
– a sage Graph
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import treelength_lowerbound sage: G = graphs.PetersenGraph() sage: treelength_lowerbound(G) 1 sage: G.treelength() 2 sage: G = graphs.CycleGraph(5) sage: treelength_lowerbound(G) 2 sage: G.treelength() 2
- sage.graphs.graph_decompositions.tree_decomposition.treewidth(g, k=None, kmin=None, certificate=False, algorithm=None)#
Compute the treewidth of \(g\) (and provide a decomposition).
INPUT:
g
– a sage Graphk
– integer (default:None
); indicates the width to be considered. Whenk
is an integer, the method checks that the graph has treewidth \(\leq k\). Ifk
isNone
(default), the method computes the optimal tree-width.kmin
– integer (default:None
); when specified, search for a tree-decomposition of width at leastkmin
. This parameter is useful when the graph can be decomposed into atoms. This parameter is ignored whenk
is notNone
or whenalgorithm == 'tdlib'
.certificate
– boolean (default:False
); whether to return the tree-decomposition itself.algorithm
– whether to use"sage"
or"tdlib"
(requires the installation of the ‘tdlib’ package). The default behaviour is to use ‘tdlib’ if it is available, and Sage’s own algorithm when it is not.
OUTPUT:
g.treewidth()
returns the treewidth ofg
. Whenk
is specified, it returnsFalse
when no tree-decomposition of width \(\leq k\) exists orTrue
otherwise. Whencertificate=True
, the tree-decomposition is also returned.ALGORITHM:
This function virtually explores the graph of all pairs
(vertex_cut,cc)
, wherevertex_cut
is a vertex cut of the graph of cardinality \(\leq k+1\), andconnected_component
is a connected component of the graph induced byG-vertex_cut
.We deduce that the pair
(vertex_cut,cc)
is feasible with tree-width \(k\) ifcc
is empty, or if a vertexv
fromvertex_cut
can be replaced with a vertex fromcc
, such that the pair(vertex_cut+v,cc-v)
is feasible.Note
The implementation would be much faster if
cc
, the argument of the recursive function, was a bitset. It would also be very nice to not copy the graph in order to compute connected components, for this is really a waste of time.See also
path_decomposition()
computes the pathwidth of a graph. See also thevertex_separation
module.EXAMPLES:
The PetersenGraph has treewidth 4:
sage: graphs.PetersenGraph().treewidth() 4 sage: graphs.PetersenGraph().treewidth(certificate=True) Tree decomposition: Graph on 6 vertices
The treewidth of a 2d grid is its smallest side:
sage: graphs.Grid2dGraph(2,5).treewidth() 2 sage: graphs.Grid2dGraph(3,5).treewidth() 3
When parameter
kmin
is specified, the method search for a tree-decomposition of width at leastkmin
:sage: g = graphs.PetersenGraph() sage: g.treewidth() 4 sage: g.treewidth(kmin=2, algorithm='sage') 4 sage: g.treewidth(kmin=g.order(), certificate=True, algorithm='sage') Tree decomposition: Graph on 1 vertex
- sage.graphs.graph_decompositions.tree_decomposition.width_of_tree_decomposition(G, T, check=True)#
Return the width of the tree decomposition \(T\) of \(G\).
The width of a tree-decomposition is the size of the largest bag minus 1. The empty graph and a graph of order 1 have treewidth 0.
INPUT:
G
– a sage GraphT
– a tree-decomposition for \(G\)check
– boolean (default:True
); whether to check that the tree-decomposition \(T\) is valid for \(G\)
EXAMPLES:
sage: from sage.graphs.graph_decompositions.tree_decomposition import width_of_tree_decomposition sage: G = graphs.PathGraph(3) sage: T = G.treewidth(certificate=True) sage: width_of_tree_decomposition(G, T, check=True) 1