Schonende Einführung in die algorithmischen Aspekte der Baumtiefe

13

Treewidth und Pathwidth sind beliebte Parameter, die die Nähe eines Graphen zu einem Baum bzw. Pfad messen. Tatsächlich scheint die Baumbreite so populär zu sein, dass sie in vielen Artikeln, Büchern und Vorlesungsskripten vorkommt, die (auch sehr sanfte) Einführungen in die algorithmischen Aspekte der Baumbreite geben (siehe z. B. das Buch Downey & Fellows). Typischerweise erklären diese Ressourcen, wie ein NP-hartes Problem (zB eine unabhängige Menge) in der Polynomzeit durch dynamisches Programmieren auf einer Baumzerlegung gelöst wird.

Es ist jedoch manchmal der Fall, dass ein Graphproblem sowohl für Graphen mit begrenzter Baumbreite als auch für Graphen mit begrenzter Pfadbreite NP-vollständig bleibt. Solche Härteergebnisse implizieren jedoch keine Härte für eine begrenzte Baumtiefe , die informell die Nähe zu einem Stern misst.

Es scheint fair zu sein, zu sagen, dass die Baumtiefe nicht so weit verbreitet ist wie die Baumbreite. Für jemanden, der mehr über Algorithmen lernen möchte, die anhand der Baumtiefe parametrisiert werden, gibt es (ähnlich wie bei der Baumbreite) einige nützliche Ressourcen, um zu lernen, wie solche Algorithmen möglicherweise normalerweise funktionieren.

Juho
quelle

Antworten:

10

Meine Lieblingsressource zu diesem Thema ist das Buch Sparsity von Jaroslav Nešetřil und Patrice Ossona de Mendez. Es enthält eine Menge Material speziell zur Baumtiefe, einschließlich algorithmischer Aspekte. Und für eine kurze und schnelle Einführung gibt es immer den Wikipedia-Artikel .

David Eppstein
quelle
@Juho Auch Kapitel 6 des Buches Graph Colorings befasst sich mit dem Vertex-Ranking (auch als geordnete Färbung bezeichnet). Die Farbtiefe entspricht der Farbzahl dieser Farbvariante. Das Buchkapitel beschreibt einfache Algorithmen (zum Beispiel auf Bäumen).
Cyriac Antony