Although there exists methods and implementations for checking whether a graph has treewidth k [1], there does not exist any implementation of generating a random graph with treewidth k. To this end, the goal of this project is to investigate and come up with approaches to generate random graphs, with some given prior (e.g., independent edges like Erdos-Renyi graphs [2]), that have a treewidth of k.

Requirements:

• Knowledge of graphs and basic graph algorithms (like DFS and BFS).
• Knowledge of either Python or Julia.

If interested, please send your CV and transcript to Sepehr Elahi at sepehr.elahi@epfl.ch

References:

[1] Wikipedia contributors. (2023, July 31). Treewidth. In Wikipedia, The Free Encyclopedia. Retrieved November 3, 2023, from https://en.wikipedia.org/w/index.php?title=Treewidth

[2] Wikipedia contributors. (2023, October 8). Erdős–Rényi model. In Wikipedia, The Free Encyclopedia. Retrieved November 4, 2023, from https://en.wikipedia.org/w/index.php?title=Erdős–Rényi_model