University of Primorska Faculty of Mathematics, Natural Sciences and Information Technologies

Mathematical Research Seminar

Mathematical research seminar is organized by the departments of Mathematics of two members of the University - UP FAMNIT and Andrej Marušič Institute (UP IAM), every Monday from October to June.

You are cordially invited to attend the lectures.

Datum in ura / Date and time: 27.5.24
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tara Abrishami (University of Hamburg)
Naslov / Title: Induced matching treewidth and the maximum independent set problem
Vsebina / Abstract:

Width parameters such as treewidth, the most prominent width parameter, are graph invariants that roughly measure how complicated a graph is. Several width parameters have algorithmic implications; for example, many NP-hard problems can be solved in polynomial time in graphs of bounded treewidth. On the other hand, there exist graph classes with unbounded treewidth but which do admit fast algorithms for hard problems, so in this sense treewidth does a poor job of capturing the solvability of hard problems. Several new width parameters have recently been introduced to better represent the solvability of the maximum independent set problem. In this talk, I will discuss results and problems related to one of these width parameters, called induced matching treewidth.

This talk is based on joint work with Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Paweł Rzążewski, and Bartosz Walczak.