Naukowiec z MINI PW z grantem SONATA BIS-14

Dr hab. inż. Paweł Rzążewski z Wydziału Matematyki i Nauk Informacyjnych PW zdobył grant w konkursie Narodowego Centrum Nauki SONATA BIS-14. Projekt „Od grafów gęstych do rzadkich i z powrotem” otrzymał dofinansowanie w wysokości 1 847 080 zł.

Granty w ramach konkursu SONATA BIS-14 przyznawane są na projekty badawcze mające na celu powołanie nowego zespołu naukowego, realizowane przez osoby posiadające stopień naukowy lub tytuł naukowy, które uzyskały stopień naukowy doktora w okresie od 5 do 12 lat przed złożeniem wniosku.

Środki otrzymane w ramach konkursu można przeznaczyć na wynagrodzenia dla zespołu badawczego, w tym również stypendia dla studentów lub doktorantów, zakup lub wytworzenie aparatury naukowo-badawczej oraz inne koszty związane z wydatkami niezbędnymi do realizacji projektu badawczego.

O projekcie

Już od lat siedemdziesiątych dwudziestego wieku wiemy, że istnieje wiele naturalnych problemów obliczeniowych, których (prawdopodobnie) nigdy nie będziemy w stanie rozwiązać efektywnie. Przykładem takiego problemu jest Największy Zbiór Niezależny: dla danego grafu należy znaleźć największy zbiór parami niesąsiadujących wierzchołków. Prostota definicji problemu jest zwodnicza: o ile nie wydarzy się coś bardzo niespodziewanego, nie możemy liczyć na szybkie (a nawet „istotnie szybsze niż brute-force”) algorytmy, które rozwiążą ten problem, choćby w przybliżeniu. Takie algorytmy mogą jednak istnieć, jeśli ograniczymy możliwe grafy wejściowe (instancje) to pewnej rodziny (zwanej klasą). 

Badanie problemów obliczeniowych w szczególnych klasach grafów jest bardzo aktywnym kierunkiem badań w ostatnich dziesięcioleciach. Często w tym, a także w innych kontekstach, spotykamy pewną dualność między grafami rzadkimi i gęstymi. Istnieje wiele rozsądnych definicji grafów rzadkich, ale ogólnie klasy grafów rzadkich uważane są za dobrze zrozumiane. Często mają one silne własności strukturalne, które pozwalają na przykład na ograniczenie liczby chromatycznej. W wielu przypadkach własności te mogą być też wykorzystane algorytmicznie. Liczne klasyczne problemy obliczeniowe, trudne w ogólności, stają się istotnie łatwiejsze w klasach grafów rzadkich – tj. istnieją dla nich szybkie algorytmy, przynajmniej aproksymacyjne. Z drugiej strony, grafy gęste uważane są za strukturalnie skomplikowane. Co więcej, z perspektywy obliczeniowej, często dostarczają nam wyników negatywnych.

Okazuje się jednak, że nawet pośród klas grafów gęstych można znaleźć wiele silnie ustrukturyzowanych przykładów. Intuicyjnie, będziemy zainteresowani klasami grafów, które „tylko udają, że są gęste”. Nieco bardziej formalnie, są klasy (potencjalnie gęstych) grafów, w których nadal można doszukać się pewnej rzadkiej struktury, niekoniecznie widocznej od razu. W projekcie będziemy badać, w jaki sposób wyniki otrzymane dla klas grafów rzadkich mogą być uogólnione do takich „strukturalnie rzadkich” klas. W szczególności jesteśmy zainteresowani transferem narzędzi z jednego świata do drugiego.

Co więcej, będziemy też badać klasy grafów, które „tylko udają, że są rzadkie”. Dokładniej, zajmiemy się (potencjalnie rzadkimi) grafami z ustalonym porządkiem na wierzchołkach. Relacja porządku jest gęsta, ale nadal niezbyt skomplikowana. Dzięki pierwszej z tych własności, nawet proste rodziny grafów (np. skojarzenia) są dość bogate w uporządkowanym świecie. Dzięki drugiej własności, nadal możemy liczyć na ciekawe własności strukturalne i algorytmiczne.