Ścieżka Gyárfása

Klasy grafów bez długich indukowanych ścieżek są jednymi z bardziej tajemniczych klas grafów: z jednej strony bardzo mało wiemy o ich strukturze, z drugiej strony wiele problemów algorytmicznych (np. problem największego zbioru niezależnego) nie ma dowodu NP-trudności w tych klasach grafów. András Gyárfás w latach 80., przez bardzo elegancki argument, pokazał, że grafy te mają własność zwaną chi-ograniczonością. W ostatnich latach zrozumieliśmy, jak tą technikę - zwaną ścieżką Gyárfása - użyć tez algorytmicznie. W trakcie seminarium opowiem o tym, co już wiemy, czego jeszcze nie wiemy, oraz pokażę o co chodzi w ścieżce Gyárfása.

Aby dołączyć do spotkania prosimy o skorzystanie z linku meet.google.com/xui-qqpw-fze na kilka minut przed 14:30. Osoby posiadające konto google z adresem UW prosimy o wcześniejsze zalogowanie.

Graph classes excluding long paths as induced subgraphs are one of the more mysterious graph classes: on one hand, we know very little about their structure, and on the other hand for a number of algorithmic problems (incl. maximum independent set) we do not know an NP-hardness proof on these graph classes. In the 80s, András Gyárfás, via a very elegant argument, showed that these graphs have a property called chi-boundedness. In recent years we have understood how this technique - called the Gyárfás' path - can be used also for algorithm design. During the seminar, I will discuss what we know, what we do not know yet, and show how the Gyárfás' path argument works.

In order to join the meeting please follow the link meet.google.com/xui-qqpw-fze a few minutes before 2:30 p.m. If you have a google account with a UW address, please log-in first.