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]

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), where vertex_cut is a vertex cut of the graph of length \(\leq k\), and connected_component is a connected component of the graph induced by G - vertex_cut.

We deduce that the pair (vertex_cut, connected_component) is feasible with treelength \(k\) if connected_component is empty, or if a vertex v from vertex_cut can be replaced with a vertex from connected_component, such that the pair (vertex_cut + v, connected_component - v) is feasible.

INPUT:

G – a sage Graph
k – 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\) is None (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 returns False when no tree-decomposition of length \(\leq k\) exists or True otherwise. When certificate=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 Graph
T – 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.label_nice_tree_decomposition(nice_TD, root, directed=False)#

Return a nice tree decomposition with nodes labelled accordingly.

INPUT:

nice_TD – a nice tree decomposition
root – the root of the nice tree decomposition
directed – boolean (default: False); whether to return the nice tree decomposition as a directed graph rooted at vertex root or as an undirected graph

OUTPUT:

A nice tree decomposition with nodes labelled.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition, label_nice_tree_decomposition
sage: claw = graphs.CompleteBipartiteGraph(1, 3)
sage: claw_TD = claw.treewidth(certificate=True)
sage: nice_TD = make_nice_tree_decomposition(claw, claw_TD)
sage: root = sorted(nice_TD.vertices())[0]
sage: label_TD = label_nice_tree_decomposition(nice_TD, root, directed=True)
sage: label_TD.name()
'Labelled Nice tree decomposition of Tree decomposition'
sage: for node in sorted(label_TD):  # random
....:     print(node, label_TD.get_vertex(node))
(0, {}) forget
(1, {0}) forget
(2, {0, 1}) intro
(3, {0}) forget
(4, {0, 3}) intro
(5, {0}) forget
(6, {0, 2}) intro
(7, {2}) intro
(8, {}) leaf

sage.graphs.graph_decompositions.tree_decomposition.length_of_tree_decomposition(G, T, check=True)#

Return the length of the tree decomposition \(T\) of \(G\).

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)\)). See the documentation of the tree_decomposition module for more details.

INPUT:

G – a graph
T – a tree-decomposition for \(G\)
check – boolean (default: True); whether to check that the tree-decomposition \(T\) is valid for \(G\)

EXAMPLES:

Trees and cliques have treelength 1:

sage: from sage.graphs.graph_decompositions.tree_decomposition import length_of_tree_decomposition
sage: G = graphs.CompleteGraph(5)
sage: tl, T = G.treelength(certificate=True)
sage: tl
1
sage: length_of_tree_decomposition(G, T, check=True)
1
sage: G = graphs.RandomTree(20)
sage: tl, T = G.treelength(certificate=True)
sage: tl
1
sage: length_of_tree_decomposition(G, T, check=True)
1

The Petersen graph has treelength 2:

sage: G = graphs.PetersenGraph()
sage: tl, T = G.treelength(certificate=True)
sage: tl
2
sage: length_of_tree_decomposition(G, T)
2

When a tree-decomposition has a single bag containing all vertices of a graph, the length of this tree-decomposition is the diameter of the graph:

sage: G = graphs.Grid2dGraph(2, 5)
sage: G.treelength()
2
sage: G.diameter()
5
sage: T = Graph({Set(G): []})
sage: length_of_tree_decomposition(G, T)
5

sage.graphs.graph_decompositions.tree_decomposition.make_nice_tree_decomposition(graph, tree_decomp)#

Return a nice tree decomposition (TD) of the TD tree_decomp.

See page 161 of [CFKLMPPS15] for a description of the nice tree decomposition.

A nice TD \(NT\) is a rooted tree with four types of nodes:

Leaf nodes have no children and bag size 1;
Introduce nodes have one child: If \(v \in NT\) is an introduce node and \(w \in NT\) its child, then \(Bag(v) = Bag(w) \cup \{ x \}\), where \(x\) is the introduced node;
Forget nodes have one child: If \(v \in NT\) is a forget node and \(w \in NT\) its child, then \(Bag(v) = Bag(w) \setminus \{ x \}\), where \(x\) is the forgotten node;
Join nodes have two children, both identical to the parent.

INPUT:

graph – a Sage graph
tree_decomp – a tree decomposition

OUTPUT:

A nice tree decomposition.

Warning

This method assumes that the vertices of the input tree \(tree_decomp\) are hashable and have attribute issuperset, e.g., frozenset or Set_object_enumerated_with_category.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: petersen = graphs.PetersenGraph()
sage: petersen_TD = petersen.treewidth(certificate=True)
sage: make_nice_tree_decomposition(petersen, petersen_TD)
Nice tree decomposition of Tree decomposition: Graph on 28 vertices

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: cherry = graphs.CompleteBipartiteGraph(1, 2)
sage: cherry_TD = cherry.treewidth(certificate=True)
sage: make_nice_tree_decomposition(cherry, cherry_TD)
Nice tree decomposition of Tree decomposition: Graph on 7 vertices

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: bip_one_four = graphs.CompleteBipartiteGraph(1, 4)
sage: bip_one_four_TD = bip_one_four.treewidth(certificate=True)
sage: make_nice_tree_decomposition(bip_one_four, bip_one_four_TD)
Nice tree decomposition of Tree decomposition: Graph on 15 vertices

Check that github issue #36843 is fixed:

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: triangle = graphs.CompleteGraph(3)
sage: triangle_TD = triangle.treewidth(certificate=True)
sage: make_nice_tree_decomposition(triangle, triangle_TD)
Nice tree decomposition of Tree decomposition: Graph on 7 vertices

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: graph = graphs.CompleteBipartiteGraph(2, 5)
sage: graph_TD = graph.treewidth(certificate=True)
sage: make_nice_tree_decomposition(graph, graph_TD)
Nice tree decomposition of Tree decomposition: Graph on 25 vertices

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: empty_graph = graphs.EmptyGraph()
sage: tree_decomp = empty_graph.treewidth(certificate=True)
sage: len(make_nice_tree_decomposition(empty_graph, tree_decomp))
0

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: singleton = graphs.CompleteGraph(1)
sage: tree_decomp = singleton.treewidth(certificate=True)
sage: make_nice_tree_decomposition(singleton, tree_decomp)
Nice tree decomposition of Tree decomposition: Graph on 3 vertices

sage: from sage.graphs.graph_decompositions.tree_decomposition import make_nice_tree_decomposition
sage: an_edge = graphs.CompleteGraph(2)
sage: tree_decomp = an_edge.treewidth(certificate=True)
sage: make_nice_tree_decomposition(an_edge, tree_decomp)
Nice tree decomposition of Tree decomposition: Graph on 5 vertices

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

INPUT:

G – a sage Graph
k – 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\) is None (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 returns False when no tree-decomposition of length \(\leq k\) exists or True otherwise. When certificate=True, the tree-decomposition is also returned.

ALGORITHM:

This method virtually explores the graph of all pairs (vertex_cut, connected_component), where vertex_cut is a vertex cut of the graph of length \(\leq k\), and connected_component is a connected component of the graph induced by G - vertex_cut.

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.

`treewidth()`	Compute the treewidth of \(G\) (and provide a decomposition).
`treelength()`	Compute the treelength of \(G\) (and provide a decomposition).
`make_nice_tree_decomposition()`	Return a nice tree decomposition (TD) of the TD \(tree_decomp\).
`label_nice_tree_decomposition()`	Return a nice tree decomposition with nodes labelled accordingly.
`is_valid_tree_decomposition()`	Check whether \(T\) is a valid tree-decomposition for \(G\).
`reduced_tree_decomposition()`	Return a reduced tree-decomposition of \(T\).
`width_of_tree_decomposition()`	Return the width of the tree decomposition \(T\) of \(G\).
`length_of_tree_decomposition()`	Return the length of the tree decomposition \(T\) of \(G\).