In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the tree-depth of a
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is a numerical
invariant of
, the minimum height of a
Trémaux tree
In graph theory, a Trémaux tree of an undirected graph G is a type of spanning tree, generalizing depth-first search trees.
They are defined by the property that every edge of G connects an ancestor–descendant pair in the tree. Trémaux trees ar ...
for a
supergraph of
. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the
cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a
digraph is to a directed acyclic graph (DAG), in the sense that a DAG has
...
of
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s and the
star height of
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s. Intuitively, where the
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
of a graph measures how far it is from being a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, this parameter measures how far a graph is from being a
star.
Definitions
The tree-depth of a graph
may be defined as the minimum height of a
forest
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
with the property that every edge of
connects a pair of nodes that have an ancestor-descendant relationship to each other in
. If
is connected, this forest must be a single tree; it need not be a subgraph of
, but if it is, it is a
Trémaux tree
In graph theory, a Trémaux tree of an undirected graph G is a type of spanning tree, generalizing depth-first search trees.
They are defined by the property that every edge of G connects an ancestor–descendant pair in the tree. Trémaux trees ar ...
for
.
The set of ancestor-descendant pairs in
forms a
trivially perfect graph
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were na ...
, and the height of
is the size of the largest
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
in this graph. Thus, the tree-depth may alternatively be defined as the size of the largest clique in a trivially perfect supergraph of
, mirroring the definition of
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
as one less than the size of the largest clique in a
chordal supergraph of
.
Another definition is the following:
where
is the set of vertices of
and the
are the connected components of
. This definition mirrors the definition of
cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a
digraph is to a directed acyclic graph (DAG), in the sense that a DAG has
...
of directed graphs, which uses strong connectivity and strongly connected components in place of undirected connectivity and connected components.
Tree-depth may also be defined using a form of
graph coloring. A centered coloring of a graph is a coloring of its vertices with the property that every connected
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
has a color that appears exactly once. Then, the tree-depth is the minimum number of colors in a centered coloring of the given graph. If
is a forest of height
with the property that every edge of
connects an ancestor and a descendant in
, then a centered coloring of
using
colors may be obtained by coloring each vertex by its distance from the root of its tree in
.
Finally, one can define this in terms of a
pebble game
In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules:
* A given step of the game consists of either placing a pebble on an ...
, or more precisely as a
cops and robber game. Consider the following game, played on an undirected graph. There are two players, a robber and a cop. The robber has one pebble he can move along the edges of the given graph. The cop has an unlimited number of pebbles, but she wants to minimize the amount of pebbles she uses. The cop cannot move a pebble after it has been placed on the graph. The game proceeds as follows. The robber places his pebble. The cop then announces where she wants to place a new cop pebble. The robber can then move his pebble along edges, but not through occupied vertices. The game is over when the cop player places a pebble on top of the robber pebble. The tree-depth of the given graph is the minimum number of pebbles needed by the cop to guarantee a win. For a
star graph, two pebbles suffice: the strategy is to place a pebble at the center vertex, forcing the robber to one arm, and then to place the remaining pebble on the robber. For a
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
with
vertices, the cop uses a
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
strategy, which guarantees that at most
pebbles are needed.
Examples
![Tree-depth](https://upload.wikimedia.org/wikipedia/commons/2/2d/Tree-depth.svg)
The tree-depth of a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
equals its number of vertices. For, in this case, the only possible forest
for which every pair of vertices are in an ancestor-descendant relationship is a single path. Similarly, the tree-depth of a
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
is
. For, the nodes that are placed at the leaves of the forest
must have at least
ancestors in
. A forest achieving this
bound may be constructed by forming a path for the smaller side of the bipartition, with each vertex on the larger side of the bipartition forming a leaf in
connected to the bottom vertex of this path.
The tree-depth of a path with
vertices is exactly
. A forest
representing this path with this depth may be formed by placing the midpoint of the path as the root of
and recursing within the two smaller paths on either side of it.
Depth of trees and relation to treewidth
Any
-vertex
forest
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
has tree-depth
. For, in a forest, one can always find a constant number of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most
vertices each. By recursively partitioning each of these two subforests, one can easily derive a logarithmic upper bound on the tree-depth. The same technique, applied to a
tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees ...
of a graph, shows that, if the
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
of an
-vertex graph
is
, then the tree-depth of
is
. Since
outerplanar graph
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
s,
series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s, and
Halin graph
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.
The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none o ...
s all have bounded treewidth, they all also have at most logarithmic tree-depth. The typical graphs with large treedepth and small treewidth are the
perfect binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s and the paths. Precisely, there is a constant
with the following property: if a graph has treedepth at least
and treewidth less than
then it contains a perfect binary tree with height
or a path of length
as a minor.
In the other direction, the treewidth of a graph is at most equal to its tree-depth. More precisely, the treewidth is at most the
pathwidth
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition ...
, which is at most one less than the tree-depth.
Graph minors
A
minor of a graph
is another graph formed from a subgraph of
by contracting some of its edges. Tree-depth is monotonic under minors: every minor of a graph
has tree-depth at most equal to the tree-depth of
itself. Thus, by the
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...
, for every fixed
the set of graphs with tree-depth at most
has a finite set of
forbidden minors.
If
is a class of graphs closed under taking graph minors, then the graphs in
have tree-depth
if and only if
does not include all the
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
s.
[, Proposition 6.4, p. 122.]
More precisely, there is a constant
such that every graph of treedepth at least
contains one of the following minors (each of treedepth at least
):
* the
grid,
* the complete binary tree of height
,
* the path of order
.
Induced subgraphs
As well as behaving well under graph minors, tree-depth has close connections to the theory of
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
s of a graph. Within the class of graphs that have tree-depth at most
(for any fixed integer
), the relation of being an induced subgraph forms a
well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, \ldots from X contains an increasing pair x_i \leq x_j with i x_2> \cdots) nor infinite sequenc ...
. The basic idea of the proof that this relation is a well-quasi-ordering is to use induction on
; the forests of height
may be interpreted as sequences of forests of height
(formed by deleting the roots of the trees in the height-
forest) and
Higman's lemma
In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if w_1, w_2, \ldots is an infinite sequence of words over some fixed ...
can be used together with the induction hypothesis to show that these sequences are well-quasi-ordered.
Well-quasi-ordering implies that any property of graphs that is monotonic with respect to induced subgraphs has finitely many forbidden induced subgraphs, and therefore may be tested in polynomial time on graphs of bounded tree-depth. The graphs with tree-depth at most
themselves also have a finite set of forbidden induced subgraphs.
If
is a class of graphs with bounded
degeneracy, the graphs in
have bounded tree-depth if and only if there is a path graph that cannot occur as an induced subgraph of a graph in
.
Complexity
Computing tree-depth is computationally hard: the corresponding decision problem is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
.
[.] The problem remains NP-complete for
bipartite graphs , as well as for
chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
s.
On the positive side, tree-depth can be computed in
polynomial time on interval graphs, as well as on permutation, trapezoid, circular-arc, circular permutation graphs, and cocomparability graphs of bounded dimension. For undirected trees, tree-depth can be computed in linear time.
give an
approximation algorithm for tree-depth with an approximation ratio of
, based on the fact that tree-depth is always within a logarithmic factor of the treewidth of a graph.
Because tree-depth is monotonic under graph minors, it is
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
: there is an algorithm for computing tree-depth running in time where
is the depth of the given graph and
is its number of vertices. Thus, for every fixed value of
, the problem of testing whether the tree-depth is at most
can be solved in
polynomial time. More specifically, the dependence on
in this algorithm can be made linear, by the following method: compute a depth first search tree, and test whether this tree's depth is greater than
. If so, the tree-depth of the graph is greater than
and the problem is solved. If not, the shallow depth first search tree can be used to construct a
tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees ...
with bounded width, and standard
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
techniques for graphs of bounded treewidth can be used to compute the depth in linear time.
[, p. 138. A more complicated linear time algorithm based on the planarity of the excluded minors for tree-depth was given earlier by . For improved parameterized algorithms see .]
It is also possible to compute the tree-depth exactly, for graphs whose tree-depth may be large, in time
for a constant
slightly smaller than 2.
Notes
References
*.
*
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*{{citation
, last1 = Schäffer , first1 = Alejandro A.
, doi = 10.1016/0020-0190(89)90161-0
, title = Optimal node ranking of trees in linear time
, journal =
Information Processing Letters
, volume = 33
, pages = 91–96
, year = 1989, hdl = 10338.dmlcz/140723, hdl-access = free.
Graph coloring
Graph invariants
Graph minor theory