teaching:ss21:lab-ca

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:

Week | Date | |
---|---|---|

14 | 07.04.2021 at 11:00 | Initial meeting |

15 | 13.04.2021 at 16:00 | Meeting: Chose 2 heuristics you are interested in |

16 | 22.04.2021 at 12:15 | Individual short presentations 1 |

17 | 29.04.2021 at 12:15 | Individual short presentations 2 + OGDF + choose 2 algorithms to implement |

18 | 06.05.2021 at 12:15 | OGDF setup |

19 | individual meetings | Start implementation with pair programming |

20 | 20.05.2021 at 12:15 | Data structure for Tree Decomposition & OGDF questions |

21 | individual meetings | Develop idea to convert bags into tree decomposition (Pentecost week) |

22 | 02.06.2021 at 15:15 | Discussed 2 ideas to convert bags into tree decomposition, data structure, std lib vs OGDF, final report structure |

23 | 10.06.2021 at 12:15 | Mistake in LexBFS Algo, test setup, implement data structure |

24 | 17.06.2021 at 12:15 | Fixed LexBFS, Test setup, implement data structure, Chose Algo that converts bags into tree decomposition |

25 | 24.06.2021 at 12:15 | Test setup, implement Algo that converts bags into tree decomposition, naming convention in code |

26 | 01.07.2021 at 12:15 | Test results, questions about presentation, done programming |

27 | 08.07.2021 at 12:15 | Test evaluation, presentation structure |

28 | 15.07.2021 at 12:15 | Feedback on presentation slides |

29 | 22.07.2021 at 12:15 | final presentation |

33 | 16.08.2021 | first draft of final report due |

35 | 05.09.2021 | final report due |

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**

**OGDF**

**Literatur search**

_{Dozentinnen: Mutzel, Dahn}

teaching/ss21/lab-ca.txt · Last modified: 2021/11/15 18:59 by christine.dahn