<p>My favorite resource for this subject is the book <em>Sparsity</em> by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always <a href="https://en.wikipedia.org/wiki/Tree-depth">the Wikipedia article</a>.</p>

CC BY-SA 4.0
2020-01-31T06:19:43.080Z
@Juho Also, chapter 6 of the book [Graph Colorings](https://bookstore.ams.org/conm-352) is on vertex ranking (also called ordered colouring). Treedepth is same as the chromatic number of this coloring variant. The book chapter describes simple algorithms (for instance, on trees).
Cyriac Antony
CC BY-SA 3.0
2015-07-08T05:31:10.193Z
2015-07-08T05:31:10.193Z
David Eppstein
<p>Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and lecture notes that give (even very gentle) introductions to the algorithmic aspects of treewidth (see e.g. the Downey &amp; Fellows book). Typically, these resources explain how some NP-hard problem (e.g. independent set) is solved in polynomial time through dynamic programming on a tree decomposition.</p>

<p>However, it is sometimes the case a graph problem remains NP-complete for both bounded treewidth and bounded pathwidth graphs. But such hardness results don't imply hardness for bounded <a href="https://en.wikipedia.org/wiki/Tree-depth">tree-depth</a>, which informally measures the closeness to a star.</p>

<p>It seems fair to say tree-depth is not as widely known as treewidth. For someone wanting to learn more about algorithms parameterizing by tree-depth, are there (similarly to treewidth) some nice resources available for learning how such algorithms perhaps typically work?</p>

<reference-request><graph-algorithms><parameterized-complexity>
Gentle introduction to the algorithmic aspects of tree-depth
Juho
# Gentle introduction to the algorithmic aspects of tree-depth

(Asked by: username_0 on 2015-07-07)

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and lecture notes that give (even very gentle) introductions to the algorithmic aspects of treewidth (see e.g. the Downey & Fellows book). Typically, these resources explain how some NP-hard problem (e.g. independent set) is solved in polynomial time through dynamic programming on a tree decomposition.

However, it is sometimes the case a graph problem remains NP-complete for both bounded treewidth and bounded pathwidth graphs. But such hardness results don't imply hardness for bounded [tree-depth](https://en.wikipedia.org/wiki/Tree-depth), which informally measures the closeness to a star.

It seems fair to say tree-depth is not as widely known as treewidth. For someone wanting to learn more about algorithms parameterizing by tree-depth, are there (similarly to treewidth) some nice resources available for learning how such algorithms perhaps typically work?

**Tags:** reference-request, graph-algorithms, parameterized-complexity


---

## 1 answers

### Answer by username_1 on 2015-07-08. Score: 10 | Accepted answer

My favorite resource for this subject is the book *Sparsity* by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always [the Wikipedia article](https://en.wikipedia.org/wiki/Tree-depth).

> **Comments:**
> **username_2**: @username_0 Also, chapter 6 of the book [Graph Colorings](https://bookstore.ams.org/conm-352) is on vertex ranking (also called ordered colouring). Treedepth is same as the chromatic number of this coloring variant. The book chapter describes simple algorithms (for instance, on trees).  

---

