# 186.856 Structural Decompositions and Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2024S 2023S 2022S 2021S 2020S 2019S 2017S 2016S

2024S, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• LectureTube course
• Format: Presence

## Learning outcomes

After successful completion of the course, students are able to...

- design algorithms that use the decompositions associated with parameters such as treewidth, clique-width, and hypertree-width to solve problems efficiently.

- represent problems in artificial intelligence and database theory using different graph models (primal graph, incidence graph, hypergraph).

- prove upper and lower bounds for (some) width parameters in simple cases.

## Subject of course

Many combinatorial problems that are intractable in general can be efficiently solved on tree-like structures. Width parameters measuring "tree-likeness" and their corresponding decompositions can be used to design algorithms that are fast as long as the width of the input is reasonably small.

The course will cover common graph and hypergraph width parameters and some of their applications in AI and database theory. Specifically, we will discuss the graph measure tree-width and generalizations such as clique-width and rank-width. We then proceed to discuss hypergraph width parameters like hypertree-width and fractional hypertree-width.

We will also showcase applications of width parameters to problems such as propositional model counting, conjunctive query evaluation, and inference in Bayesian Networks.

## Teaching methods

Students will complete a short project, which could be some implementation or a short write-up.

## Mode of examination

Immanent

Kickoff ZOOM link (or in person in FAV 01 B)

https://tuwien.zoom.us/j/66275772564?pwd=eElGUHBraGpSWHJKZ3FNQmhGYkJhdz09

ECTS Breakdown:

20 h lectures (videos for online participants) and readings
45 h project or solving exercise sheets
10 h presentation of project or exercises
-------------------------------------
75 h total

## Course dates

DayTimeDateLocationDescription
Wed10:00 - 11:0006.03.2024Seminarraum FAV 01 B (Seminarraum 187/2) Kickoff
Mon10:00 - 13:0008.04.2024 - 29.04.2024Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Thu11:00 - 14:0011.04.2024 - 25.04.2024Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Structural Decompositions and Algorithms - Single appointments
DayDateTimeLocationDescription
Wed06.03.202410:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Kickoff
Mon08.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Thu11.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Mon15.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Thu18.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Mon22.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Thu25.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Mon29.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture

## Examination modalities

The grade is based on an informal oral presentation of the project. Further options will be discussed in the lecture.

## Course registration

Begin End Deregistration end
26.02.2024 00:00 30.04.2024 00:00 30.04.2024 00:00

## Curricula

Study CodeObligationSemesterPrecon.Info
066 645 Data Science Not specified
066 646 Computational Science and Engineering Not specified
066 926 Business Informatics Not specified
066 931 Logic and Computation Not specified
066 937 Software Engineering & Internet Computing Not specified
066 938 Computer Engineering Mandatory elective

## Literature

- Jörg Flum, Martin Grohe: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer 2006.

- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015.

## Previous knowledge

This course requires familiarity with fundamental graph theoretic definitions as well as basic knowledge of algorithmics and complexity theory. Knowledge of the topics covered in the "Algorithmics" course is an advantage.

English