13
$\begingroup$

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, 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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Juho Also, chapter 6 of the book Graph Colorings 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). $\endgroup$
    – Cyriac Antony
    Commented Jan 31, 2020 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.