Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey

Hans L. Bodlaender

doi:10.1007/978-3-031-75409-8_1

Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey

Hans L. Bodlaender^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers
Editors	Daniel Kráľ, Martin Milanič
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	3-18
Number of pages	16
ISBN (Print)	9783031754081
DOIs	https://doi.org/10.1007/978-3-031-75409-8_1
Publication status	Published - 2025
Event	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 - Gozd Martuljek, Slovenia Duration: 19 Jun 2024 → 21 Jun 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14760 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024
Country/Territory	Slovenia
City	Gozd Martuljek
Period	19/06/24 → 21/06/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

Approximation
Graph Algorithms
Pathwidth
Treedepth
Treewidth

Access to Document

10.1007/978-3-031-75409-8_1

Cite this

Bodlaender, H. L. (2025). Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. In D. Kráľ, & M. Milanič (Eds.), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers (pp. 3-18). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14760 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-75409-8_1

Bodlaender, Hans L. / Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. editor / Daniel Kráľ ; Martin Milanič. Springer Science and Business Media Deutschland GmbH, 2025. pp. 3-18 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{51724ebdd52d421a9e663437b80a7433,

title = "Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey",

abstract = "This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.",

keywords = "Approximation, Graph Algorithms, Pathwidth, Treedepth, Treewidth",

author = "Bodlaender, {Hans L.}",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 ; Conference date: 19-06-2024 Through 21-06-2024",

year = "2025",

doi = "10.1007/978-3-031-75409-8_1",

language = "English",

isbn = "9783031754081",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "3--18",

editor = "Daniel Kr{\'a}{\v I} and Martin Milani{\v c}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers",

address = "Germany",

}

Bodlaender, HL 2025, Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. in D Kráľ & M Milanič (eds), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14760 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 3-18, 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024, Gozd Martuljek, Slovenia, 19/06/24. https://doi.org/10.1007/978-3-031-75409-8_1

Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. / Bodlaender, Hans L.
Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. ed. / Daniel Kráľ; Martin Milanič. Springer Science and Business Media Deutschland GmbH, 2025. p. 3-18 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14760 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey

AU - Bodlaender, Hans L.

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.

AB - This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.

KW - Approximation

KW - Graph Algorithms

KW - Pathwidth

KW - Treedepth

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85218472624&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-75409-8_1

DO - 10.1007/978-3-031-75409-8_1

M3 - Conference contribution

AN - SCOPUS:85218472624

SN - 9783031754081

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 18

BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers

A2 - Kráľ, Daniel

A2 - Milanič, Martin

PB - Springer Science and Business Media Deutschland GmbH

T2 - 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024

Y2 - 19 June 2024 through 21 June 2024

ER -

Bodlaender HL. Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. In Kráľ D, Milanič M, editors, Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2025. p. 3-18. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-75409-8_1