You are not logged in |
Gyárfás' path
- Speaker(s)
- Marcin Pilipczuk
- Affiliation
- Instytut Informatyki
- Date
- April 22, 2021, 2:30 p.m.
- Information about the event
- Google Meet
- Title in Polish
- Ścieżka Gyárfása
- Seminar
- Colloquium Of MIM
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.
