Trees form a unique graph class for which many NP-hard problems can be solved in polynomial and often linear time. The property of how tree-like a graph is, was defined by Robertson and Seymour in 1983: the tree-width of a graph. The tree-width of a graph is defined by the smallest tree-decomposition of the graph.

For graphs with bounded tree-width many NP-hard problems (eg. the Max-Cut problem) can be solved in polynomial time. Given a tree-decomposition of a graph with a small (or constant) tree-width the Max-Cut can be calculated in linear time.

No prior knowledge of tree-decompositions or parameterized algorithms is required. The knowledge from the class Advanced Algorithms (WS 2020/21) is helpful, but not mandatory.

Keywords: Tree-width, Tree-decomposition, parameterized algorithms, Graph algorithms, Maximum Cut

You need a CS account from GSG to use Gitlab, BBB or overleaf (all hosted by the GSG). You can apply for it here.

The weekly meetings will be on Thursdays at 12:15.

The lab will be held completely in digital manner. We will use a web conference system (e.g. Zoom, or similar). Contact Christine Dahn to get the invitation link to the conference.

Attending the initial meeting on Wed. 07.04.2021 11:00 o'clock is mandatory for joining the lab.

If you are interested in joining this lab, write an email to christine.dahn [add] cs.uni-bonn.de until 31.03.2021.

In the first meeting we will give a short introduction to the topic of the Lab. Furthermore, all organizational questions will be answered. Official registration of the students to the lab can be done in the following weeks. The exact date until when the students need to be registered will be announced in a following meeting.

The following plan will be updated regularly:

For preparation, we suggest reading the following papers:

Tree-width

• Koster, Arie MCA, Hans L. Bodlaender, and Stan PM Van Hoesel. "Treewidth: computational experiments." Electronic Notes in Discrete Mathematics 8 (2001): 54-57. (Main paper)
• Bodlaender, H. L. "A Tourist Guide through Treewidth." Acta Cybernetica 11, 1-23 (1993). (focus on chapter 4: “Bounded treewidth and linear time algorithms”)

Max Cut

• Bodlaender, Hans L., and Klaus Jansen. "On the complexity of the maximum cut problem." Annual Symposium on Theoretical Aspects of Computer Science. Springer, Berlin, Heidelberg, 1994. (Relevant is only the chapter „Graphs with bounded treewidth“; depending on the version of the paper it is chaper 3.2, 5.2 or 6.)

OGDF

• Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, Petra Mutzel: The Open Graph Drawing Framework (OGDF). Chapter 17 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization, CRC Press, 2014.
• Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, Petra Mutzel: The Open Graph Drawing Framework. (abstract)

If you have problems accessing a paper due to a paywall, try connecting to Uni Bonn via VPN or SSH. Then most articles are available without a fee (or better yet, the Uni pays the fee). If that doesn't work, let me know.

To find different versions of an article, search the title and main author on google scholar. Click on “all X versions” below the article you are interested in (check title, authors and year) to see the different versions. Some versions are not protected by a paywall, eg. if the authors published it on their institutes website. Be careful thou, some versions are outdated and might differ to the latest version. On the other hand, other versions might explain some aspects of the paper in more detail.

Material and code

• Gitlab

OGDF

• official website
• Download over GitHub
• Documentation
• Getting started
• How-to examples

Literatur search

• dblp
• Google scholar
• arXiv

_{Dozentinnen: Mutzel, Dahn}