Logowanie do System sprawozdań KDM

Algorytmy testowania własności w wybranych modelach grafowych

Kierownik projektu: Michał Małafiejski

Politechnika Gdańska

Wydział Elektroniki, Telekomunikacji i Informatyki

Gdańsk

Streszczenie projektu

W zagadnieniach optymalizacji dyskretnej szeroko wykorzystuje się modele grafowe, zarówno z uwagi na bogactwo metod matematycznych, które można zastosować do analizy własności problemów (w tym analizy złożoności obliczeniowej, czyli możliwości konstrukcji efektywnych algorytmów dokładnych), jak i również z uwagi na wykorzystywanie wydajnych dyskretnych struktur danych wspierających konstrukcje wielomianowych algorytmów dokładnych czy przybliżonych oraz różnego rodzaju heurystyk.

W klasycznym podejściu do analizy złożoności danego problemu optymalizacyjnego bada się jego wersję decyzyjną, w której pytamy się o istnienie rozwiązania spełniającego zadane ograniczenia, precyzyjnie ustalając co stanowi wejście problemu, a co jest parametrem (niezależnym od wejścia) danego problemu. Przykładem może być problem kolorowania grafów, czyli w wersji optymalizacyjnej problem znalezienia etykietowania (kolorowania) wierzchołków grafu minimalną liczbą etykiet (kolorów) parami różnych w wierzchołkach połączonych krawędziami. W wersji decyzyjnej ogólnego problemu kolorowania pytamy się o istnienie pokolorowania liczbą kolorów podaną na wejściu (wraz z grafem). Możemy również przyjąć ograniczenie na liczbę kolorów jako parametr problemu (a nie wejścia). Przykładem jest problem 3-kolorowania grafów, który już dla grafów planarnych okazuje się być problemem NP-zupełnym, choć pokazano że dla grafów planarnych bez trójkątów problem decyzyjny jest trywialny (odpowiedź zawsze pozytywna), natomiast samo 3-pokolorowanie grafów planarnych bez trójkątów można skonstruować w czasie O(nlogn).

Dla trudnych obliczeniowo (NP-trudnych) problemów optymalizacyjnych, dla których nie istnieją wielomianowe algorytmy dokładne (o ile P różne NP) bada się możliwości konstrukcji wielomianowych algorytmów przybliżonych lub schematów aproksymacyjnych. Dla problemów decyzyjnych bada się możliwości konstrukcji tzw. testerów własności (ang. property testers) będących pewnego rodzaju odpowiednikiem schematów aproksymacyjnych dla problemów optymalizacyjnych. Testery własności sa sparametryzowanymi algorytmami probabilistycznymi, które dla pewnego podzbioru danych wejściowych (im mniejszy parametr tym większy zbiór takich danych wejściowych) udzielają poprawnej odpowiedzi (tak lub nie) z odpowiednio wysokim (ustalonym i niezależnym od parametru) prawdopodobieństwem.

Podstawowa tematyka projektu będzie dotyczyła możliwości konstrukcji wielomianowych algorytmów dla problemów trudnych obliczeniowo, zarówno w wersji optymalizacyjnej (algorytmy przybliżone) jak i decyzyjnej (testery własności), głównie dla problemów sformułowanych z wykorzystaniem modeli grafowych: bezpieczeństwa w grafach (koalicje, zbiory bezpieczne), kolorowania (modele końcówkowe), dominowania (totalne dominowanie i warianty) oraz podziałów i pokryć (P3-pokrycia).

W ramach prowadzonych badań planowane są wyczerpujące testy dla małych klas grafów umożliwiające weryfikację lub dostarczenie solidnych przesłanek dla wielu otwartych problemów m.in. zgłoszonego przez Paula Seymoura problemu dotyczącego charakteryzacji nie dwudzielnych hipergrafów 3-uniform oraz 3-regular (która ma związek z problemami totalnego dominowania lub równowagi strategicznej w grafach kubicznych) czy hipotezy Fulkersona-Berge'a dotyczącej istnienia szczególnych doskonałych skojarzeń (ang. perfect matchings).

Publikacje

  1. Mateusz Pabiś, Przeszukiwanie przestrzeni rozwiązań problemów grafowych na klastrach obliczeniowych, Politechnika Gdańska 1, (2015) 1-45

Centrum Informatyczne Trójmiejskiej Akademickiej Sieci Komputerowej
ul. G. Narutowicza 11/12, 80-233 Gdańsk   |   tel. 58-347-24-11
email: office@task.gda.pl   |   NIP: 584-020-35-93