Tree-depth

Tree-depth is a graph invariant in graph theory that quantifies the structural complexity of a connected undirected graph G by measuring the minimum height of a rooted forest F—often called an elimination forest—such that G is a subgraph of the closure of F, where the closure of F includes all original edges of F plus additional edges connecting every pair of vertices with an ancestor-descendant relationship in F.^[1] This height is defined as the length of the longest path from a root to a leaf in F, counting the number of vertices along that path.^[2] For disconnected graphs, the tree-depth is the maximum tree-depth over its connected components.^[3] The concept was introduced by Jaroslav Nešetřil and Patrice Ossona de Mendez in 2006.^[1] Intuitively, tree-depth assesses how far a graph deviates from being a star—a tree with one central vertex connected to all others—much like treewidth measures deviation from being a tree in general, though tree-depth is a stricter parameter that always satisfies treewidth(G) ≤ tree-depth(G) ≤ treewidth(G) · log₂(|V(G)| + 1).^[4] It is minor-monotone, meaning that if H is a minor of G, then tree-depth(H) ≤ tree-depth(G), and it is bounded for any proper minor-closed graph class.^[1] Graphs with bounded tree-depth exhibit sparsity properties that facilitate efficient algorithms, and complete graphs K_n achieve the maximum tree-depth of ⌈log₂(n + 1)⌉ among n-vertex graphs. Tree-depth admits several equivalent characterizations, including the minimum height of a Trémaux tree for a supergraph of G (a rooted tree where edges connect ancestors to descendants).^[5] It also corresponds to the winning strategy length in a game-theoretic selection-deletion game on G, where one player selects vertices to eliminate components while the other aims to prolong the process.^[3] Notable applications of tree-depth arise in parameterized complexity and structural graph theory, particularly for designing fixed-parameter tractable algorithms; for instance, subgraph isomorphism and graph isomorphism problems become solvable in time O(2^O(td(G)²) · n^O(1)) when parameterized by tree-depth td(G).^[4] It also bounds chromatic numbers in minor-closed classes, enabling results on universal graphs and homomorphism complexities, and plays a role in analyzing random graphs and sparse graph classes for algorithmic efficiency.^[1] Computing tree-depth is NP-hard but has been the focus of parameterized algorithm challenges, with practical heuristics scaling to graphs with millions of vertices.^[2]

Definitions and Characterizations

Primary Definition via Trivialization

The tree-depth of a graph G, denoted \mathrm{td}(G), is defined as the minimum height of a rooted forest F on the vertex set V(G) such that G is a subgraph of the closure of F.^[6] The closure of F, denoted \mathrm{clos}(F), is the graph obtained by adding an edge between every pair of vertices in F that are in an ancestor-descendant relationship in F.^[6] The height of a rooted forest F is the maximum height over all its trees, where the height of a tree is the number of vertices on the longest path from its root to a leaf.^[6] A single-vertex graph thus has tree-depth 1, as its trivial forest has height 1. This forest-based representation trivializes G in the sense that the partial order induced by the ancestor-descendant relation in F ensures every edge of G connects comparable elements: specifically, for any edge \{u, w\} in G, one endpoint is an ancestor of the other in F.^[6] Consequently, \mathrm{clos}(F) may contain additional edges beyond those in G, but all edges of G are preserved as ancestor-descendant connections. An equivalent recursive characterization captures this structure: for a graph G with connected components G_1, \dots, G_p, \mathrm{td}(G) = \max_i \mathrm{td}(G_i) if p > 1; if G is connected and |V(G)| = 1, then \mathrm{td}(G) = 1; otherwise, \mathrm{td}(G) = 1 + \min_{v \in V(G)} \max \{ \mathrm{td}(H) \mid H \text{ is a connected component of } G - v \}.^[6] This recursion reflects the process of selecting a root vertex v to minimize the height contributed by the substructures below it.

Equivalent Formulations

Tree-depth of a graph G, denoted \mathrm{td}(G), admits several equivalent characterizations that provide alternative perspectives on the parameter. One such formulation relates tree-depth to trivially perfect graphs, which are the chordal graphs that are also cographs and can be represented as the comparability graphs of rooted trees. Specifically, \mathrm{td}(G) is the minimum integer n such that G is a subgraph of a trivially perfect graph with maximum clique size n.^[7]^[1] Another equivalent definition arises from graph coloring, particularly centered colorings. A centered coloring of a graph G is a proper vertex coloring such that for every connected induced subgraph H of G, there exists a color that appears exactly once in H. The tree-depth \mathrm{td}(G) equals the minimum number of colors required in such a centered coloring of G, also known as the centered chromatic number \chi_c(G).^[8]^[1] Tree-depth can also be characterized through a variant of the cops-and-robbers game played on the graph. In this game, the robber first chooses and announces a starting vertex. Then, the cop sequentially places up to d cops one at a time on vertices, with the robber moving after each cop placement along any path (but not through occupied vertices) to another vertex (or staying put). The cop wins if, after the robber's move following a cop placement, the robber occupies the same vertex as that newly placed cop; otherwise, if all d cops are placed without capturing the robber, the robber wins. The tree-depth \mathrm{td}(G) is the minimum d such that the cop has a winning strategy in this game.^[4]^[1] Finally, tree-depth connects to elimination orderings via the height of an associated elimination tree. Given a linear ordering of the vertices of G, an elimination tree is constructed recursively: the last vertex in the ordering becomes a leaf connected to one of its neighbors in the remaining graph, and the process recurses on the subgraph induced by the preceding vertices after adding any necessary edges to maintain the ancestor-descendant property for edges. The tree-depth \mathrm{td}(G) is the minimum height of such an elimination tree over all possible vertex orderings.^[9]^[1]

Illustrative Examples

Basic Graph Families

The tree-depth of a path graph P_n on n vertices is \lceil \log_2 (n+1) \rceil. This value is achieved by representing the path as a subgraph of the closure of a complete binary tree of that height, where the path follows a depth-first traversal that ensures all consecutive vertices are in ancestor-descendant relation.^[1] The tree-depth of a cycle graph C_n for n \geq 3 is 3. This can be achieved with an elimination forest of height 3 where the tree is rooted such that the cycle edges are ancestor-descendant relations, for example by placing a central vertex at level 2 with branches covering the two arms of the cycle.^[10] For a forest F with n vertices, the tree-depth is O(\log n), specifically equal to the minimum height over all possible rooted representations of its components such that the forest is a subgraph of the closure. In particular, for a tree component, this corresponds to the minimum height achievable by choosing an optimal root, balancing the structure to logarithmic depth in the worst case.^[1] The tree-depth of the complete graph K_n is n, as realizing all pairwise edges in the closure necessitates a linear chain where each vertex is an ancestor of all below it, forming a path-like structure of full height.^[1]

Advanced Examples

Complete bipartite graphs provide a key example of how tree-depth captures the structural complexity in dense bipartite settings. For the complete bipartite graph K_{x,y} with x \leq y, the tree-depth is \min(x,y) + 1 = x + 1. This value is achieved by constructing an optimal elimination forest where the vertices of the smaller part form a path of length x, rooted at one end, and all vertices of the larger part are attached as children to the endpoint of this path. In this decomposition, every edge between the parts is realized as an ancestor-descendant relation, and the height of the forest is x+1. The lower bound follows from the necessity of chaining the smaller part to cover all connections without increasing the height further. Grid graphs illustrate tree-depth's sublinear scaling in geometric structures. For an m \times n grid with m \leq n, the tree-depth is at least m (equal to its tree-width) and at most O(m \log (n/m + 1)). This bound arises from a recursive subdivision construction along the longer dimension, building a balanced elimination tree that accounts for the width m while halving the length at each level. For instance, the $3 \times 3 grid has tree-depth exactly 4, as its optimal decomposition requires a height reflecting the subdivision depth and width constraints. This sublinear behavior contrasts with the linear size of the grid, highlighting tree-depth's sensitivity to recursive decomposability. Series-parallel graphs demonstrate how bounded tree-depth enforces specific recursive decompositions. In these graphs, which are built from series and parallel compositions starting from edges, a bounded tree-depth implies a hierarchical structure aligned with their construction tree, limiting the nesting depth of compositions. Outerplanar graphs, a subclass of series-parallel graphs, have tree-depth O(\log n); their planar embedding with all vertices on the outer face allows an elimination forest of logarithmic height that respects the boundary cycle and internal chords by balancing the decomposition. This bound underscores the parameter's role in certifying embeddability properties through shallow decompositions. Star graphs and their generalizations to caterpillar trees exemplify low tree-depth in tree-like structures with limited branching. A star graph K_{1,k}, consisting of a central vertex connected to k leaves, has tree-depth 2, obtained by rooting at the center with all leaves as direct children, ensuring all edges are parent-child relations. Caterpillar trees, which generalize stars by attaching leaves to a central path (the spine), inherit low tree-depth when the spine is short; the optimal decomposition roots near the spine's center, attaching pending leaves at level 2, yielding tree-depth equal to roughly half the spine length plus 1, often remaining small for compact caterpillars. This extension shows how tree-depth remains controlled in graphs close to paths with bounded appendages.

Relations to Other Parameters

Treewidth and Pathwidth

Treewidth and pathwidth are fundamental graph parameters that measure the structural complexity of graphs in terms of their distance from trees and paths, respectively. Treewidth, denoted \mathrm{tw}(G), is the minimum width over all tree decompositions of G, where the width is one less than the size of the largest bag. Pathwidth, denoted \mathrm{pw}(G), is similarly defined but restricted to path decompositions, where the underlying structure is a path rather than a general tree. These parameters form a hierarchy with tree-depth, denoted \mathrm{td}(G), satisfying the inequalities \mathrm{tw}(G) \leq \mathrm{pw}(G) \leq \mathrm{td}(G) - 1 for any graph G. The upper bound on pathwidth in terms of tree-depth follows from the fact that any path decomposition of width w can be converted into a rooted elimination tree of height at most w + 1, where the height corresponds to the tree-depth definition via trivialization. This relationship highlights how tree-depth imposes stricter structural constraints than treewidth or pathwidth. For instance, consider tree graphs T with n vertices: such graphs always have \mathrm{tw}(T) = 1, as they admit a trivial tree decomposition with singleton bags along the tree structure. However, \mathrm{td}(T) = O(\log n), achieved by balancing the elimination tree to minimize height, such as in a complete binary tree where the longest root-to-leaf path has length \Theta(\log n). In contrast, pathwidth for unbalanced trees like paths or stars can be as low as 1, but tree-depth grows logarithmically for balanced cases, illustrating the logarithmic separation possible within the hierarchy. A key structural result connects these parameters through minor obstructions. There exists an absolute constant C > 0 such that every graph G with \mathrm{td}(G) \geq C k^5 \log^2 k and \mathrm{tw}(G) < k contains either a complete binary tree of height k as a minor or a path of order $2k as a minor. This theorem, proved using recursive decomposition techniques and properties of low-treewidth graphs, implies that graphs of bounded treewidth cannot have arbitrarily high tree-depth without forcing specific expansive minor structures like branching trees or long paths. Consequently, in classes of graphs with bounded treewidth, high tree-depth necessarily introduces these minors, providing a polynomial excluded-minor characterization for approximating tree-depth within bounded-width settings.

Elimination Forests and Centered Colorings

As characterized earlier via elimination forests, the tree-depth of a graph G provides a recursive structure for decomposing the graph. An elimination forest for G is a rooted forest F on the vertex set of G such that every edge of G connects a vertex to one of its ancestors in F. The height of F is the length of the longest root-to-leaf path, and the tree-depth \text{td}(G) is the minimum height over all such elimination forests for G. In this elimination scheme, the process aligns with vertex orderings that respect the ancestor-descendant relationships in the forest. Specifically, a linear extension of the elimination forest yields an ordering where, for each vertex, its neighbors later in the ordering induce a subgraph that is contained in the subtree rooted at that vertex. The minimum height thus captures the "depth" of this elimination, distinguishing tree-depth from width-based parameters like treewidth, where the focus is on the size of neighborhoods in the remaining graph during elimination. This height-based measure emphasizes vertical structure over horizontal width, making it particularly useful for algorithms on sparse or hierarchically structured graphs.^[1] Tree-depth is equivalently defined using centered colorings, a variant of proper vertex colorings with additional connectivity constraints. A centered coloring of a graph G is a proper vertex coloring such that every connected induced subgraph of G has a color that appears exactly once in it. The centered chromatic number \chi_c(G), the minimum number of colors needed for such a coloring, equals the tree-depth \text{td}(G) for connected graphs. This equivalence arises because a centered coloring induces an elimination tree: select a vertex of a unique color as the root, recursively color the components of G minus that vertex, and the coloring ensures no edges skip levels in the tree structure. Centered colorings thus provide a combinatorial tool for bounding homomorphism numbers and solving problems like subgraph isomorphism in graphs of bounded tree-depth.^[1] Generalizations of centered colorings, such as p-centered colorings, relax the condition to require that every connected induced subgraph has at least p colors appearing exactly once. These yield upper bounds on tree-depth, with \text{td}(G) \leq \chi_{p,c}(G)^p for the p-centered chromatic number \chi_{p,c}(G), and are useful for approximating tree-depth in dense graph classes. For example, in planar grids, p-centered colorings can be constructed using O(p) colors, demonstrating efficient decompositions for geometric graphs. However, the standard centered coloring (p=1) remains the tight measure for exact tree-depth. Tree-depth relates loosely to branchwidth, another width parameter generalizing treewidth via branch-decompositions. While branchwidth \text{bw}(G) approximates treewidth within a factor of $3/2, tree-depth provides a lower bound of \text{td}(G) \geq \text{tw}(G) + 1 \geq (2/3) \text{bw}(G) + c for some constant c, reflecting its stricter hierarchical control. These bounds are heuristic and not tight, as graphs with balanced branch-decompositions can have tree-depth growing logarithmically with branchwidth in worst cases. Recent parameters like shrub-depth and twin-width connect to tree-depth through structural generalizations. Shrub-depth, a dense analog of tree-depth using node decompositions with bounded bag sizes, satisfies \text{sd}(G) \leq \text{td}(G) for any graph G, as a tree-depth decomposition induces a valid shrub-decomposition of the same depth. Twin-width, measuring distance to cluster graphs via contraction sequences, exhibits exponential gaps with tree-depth in general, though bounded twin-width implies polynomial bounds on tree-depth for certain subclasses like bipartite graphs. These ties highlight tree-depth's role in unifying sparsity measures for parameterized algorithms.^[11]^[12]

Structural Properties

Graph Minors

Tree-depth is a minor-monotone graph parameter, meaning that if H is a minor of a graph G, then \mathrm{td}(H) \leq \mathrm{td}(G). This monotonicity arises because the operations defining minors—vertex deletions, edge deletions, and edge contractions—do not increase the minimum height of an elimination forest whose closure contains the graph as a subgraph. Equality holds in many cases, such as when the minor is obtained solely by edge deletions or when contractions preserve the depth structure of the decomposition. Classes of graphs with bounded tree-depth are minor-closed, excluding certain structures as minors. In particular, every graph with tree-depth at most d excludes any path on $2^d or more vertices as a minor, since the longest path subgraph in such a graph has at most $2^d - 1 vertices. For small values of d, the excluded minors can be characterized more explicitly; graphs of tree-depth at most 2 exclude all cycles of length at least 4 (such as C_4) and certain trees (such as the path P_4) as minors, as these structures require tree-depth 3. Tree-depth also plays a role in structural theorems for minor-closed families, particularly those defined by planar obstructions. A 2025 result strengthens the classical Grid-Minor Theorem by incorporating tree-depth: for every planar graph X with \mathrm{td}(X) = h, there exists a positive integer c such that every X-minor-free graph G contains a graph H of treewidth at most $2^{h+1} - 4 such that G is isomorphic to a subgraph of H \boxtimes K_c.^[13] This structure implies large grid minors in G via the Grid-Minor Theorem, with the size exponential in h, highlighting how low tree-depth in the excluded minor X forces large grid minors in the host graph and providing tighter bounds for sparse graph classes.

Induced Subgraphs

Tree-depth is a hereditary graph parameter, meaning that if H is an induced subgraph of a graph G, then the tree-depth of H is at most the tree-depth of G. This monotonicity follows from the definition of tree-depth via rooted tree decompositions, where restricting the decomposition to the vertices of H yields a valid decomposition for H of height at most that of G.^[6] The class of all graphs with tree-depth at most d (for fixed d) forms a well-quasi-order under the induced subgraph relation. This well-quasi-ordering implies that there are no infinite descending chains or infinite antichains in this class with respect to induced subgraphs, a property first established for bounded-depth structures and extended to tree-depth. As a consequence, the class has a finite basis of minimal forbidden induced subgraphs: for each d, there exists a finite set of graphs such that a graph has tree-depth at most d if and only if it contains none of these as an induced subgraph.^[14] Examples of such forbidden induced subgraphs include long induced paths; specifically, the induced path P_t on t vertices has tree-depth \lceil \log_2 (t + 1) \rceil, so paths with $2^d or more vertices are forbidden for tree-depth at most d.^[14] More generally, the obstructions include certain trees and more complex graphs; for instance, the set of minimal forbidden induced subgraphs for tree-depth at most 3 consists of exactly 29 graphs.^[14] Graphs of bounded tree-depth have decidable monadic second-order (MSO) properties, as the well-quasi-ordering and finite forbidden sets enable effective model checking via automata on the tree decomposition. In particular, MSO model checking on such graphs can be performed in linear time for fixed formulas and bound d, equating the expressive power of first-order and MSO logic on these classes.

Algorithms and Complexity

Computational Hardness

The decision problem of determining whether the tree-depth of a graph is at most a given integer k is NP-complete. This intractability holds even when restricted to bipartite graphs.^[15] Despite the general hardness, the tree-depth can be computed in polynomial time for certain restricted graph classes. For trees, a linear-time dynamic programming algorithm suffices, as the tree-depth equals one plus the maximum tree-depth over the connected components after removing any vertex. For interval graphs, a polynomial-time algorithm exists based on finding minimum-height elimination trees using the structure of consecutive ones properties in the interval representation. In parameterized complexity, the problem is fixed-parameter tractable when parameterized by the tree-depth k itself, with algorithms running in time $2^{O(k^2)} n^{O(1)}. It is also FPT when parameterized by the vertex cover number \tau, admitting a kernel with O(\tau^3) vertices and an algorithm running in O(4^\tau \tau n) time. However, the status remains open for parameterization by treewidth. Under the Exponential Time Hypothesis (ETH), no algorithm can compute the exact tree-depth of an n-vertex graph in time $2^{o(n)} n^{O(1)}. This lower bound rules out subexponential-time solutions for the general case.

Parameterized and Approximation Algorithms

The computation of tree-depth is fixed-parameter tractable when parameterized by the tree-depth value d. A seminal algorithm by Reidl, Rossmanith, Sánchez Villaamil, and Sikdar achieves this in time $2^{O(d \log d)} n, where n is the number of vertices, through dynamic programming over potential elimination trees of depth at most d. This approach first computes a tree decomposition of width O(d), which can be approximated efficiently, and then performs dynamic programming on a nice tree decomposition to verify the existence of an elimination forest of depth d, counting valid ancestors and ensuring connectivity in subgraphs induced by subtrees. The running time arises from the state space size, which is exponential in d \log d due to the bag size and depth constraints, multiplied by linear-time processing per state. For exact computation of tree-depth without a parameter bound, simple algorithms exist that run in exponential time. Reidl et al. describe a basic dynamic programming method that decides the tree-depth in O(2^n n) time by enumerating possible roots and recursively building elimination forests, with optimizations reducing the constant factor slightly through pruning invalid branches. More advanced branch-and-bound techniques, incorporating lower bounds on depth and symmetry reduction, can further accelerate practical performance, though the worst-case remains exponential. Polynomial-time approximation algorithms provide upper bounds on tree-depth efficiently. Bodlaender, Gilbert, Hafsteinsson, and Kloks developed an O(\log n)-approximation algorithm using layered vertex separators: it recursively finds balanced separators to construct an elimination tree whose depth is at most O(\log n) times the optimal tree-depth, leveraging the fact that graphs admit separators of size related to their tree-depth. Alternatively, greedy elimination schemes, which repeatedly remove a vertex of minimum degree and adjust the structure, also yield an approximation by simulating a centroid decomposition process that bounds the recursion depth logarithmically. Recent advances (2023–2025) have extended parameterized techniques across related parameters. Pilipczuk, Pilipczuk, and Villanger introduced a deterministic algorithm computing tree-depth in $2^{O(d^2)} n time using only polynomial space, improving space efficiency for large instances via randomized sampling of elimination forests and derandomization.^[16] Additionally, unified frameworks for solving tree-depth, treewidth, and pathwidth simultaneously have emerged, often via shared dynamic programming templates on decompositions, enabling crossover applications in parameterized solvers. For special graph classes, tree-depth can be computed in linear time. Cographs, being P_4-free, admit a cotree representation computable in O(n + m) time via modular decomposition, from which the tree-depth follows directly as the height of the cotree, since cographs are exactly the graphs with clique-width 2 and bounded tree-depth aligns with this structure. Recent results show that no polynomial-time algorithm can approximate tree-depth within a factor better than 1.0003 unless P = NP.^[17] Under ETH, there is no $2^{o(n)} n^{O(1)}-time approximation algorithm.