Eksperymentalna ewaluacja algorytmów parametryzowanych i kernelizacyjnych ze szczególnym uwzględnieniem algorytmów opartych o zbiory reprezentantów.

W trakcie ostatniej dekady pojawiło się wiele nowych algorytmów parametryzowanych i kernelizacyjnych. Ponieważ w problemach z którymi się spotykamy w świecie rzeczywistym niektóre parametry często bywają małe,algorytmy takie mają potencjał być przydatnym narzędziem do ich rozwiązywania. Z tego powodu, w ostatnich latach możemy zaobserwować wzrost zainteresowania ich eksperymentalną ewaluacją, objawiający się pojawiającymi się artykułami poruszającymi tę tematykę.Ta praca magisterska jest podsumowaniem mojej pracy w projekcie "Recent trends in kernelization: theory and experimental evaluation". Podążając za obecnymi trendami, ekperymentujemy z kilkoma naszymi implementacjami bazującymi na nowych podejściach FPT, w szczególności tych używających zbiorów reprezentantów. Ponadtoudostępniamy repozytoria z naszym kodem, potrzebnym do reprodukcji wyników.W pierwszej części porównujemy kilka podejść do znajdowania cyklu Hamiltona na grafach o małej szerokości drzewowej, korzystając z dekompozycji drzewowych. Algorytmami na których się skupiamy są podejście naiwne, dwa podejścia używające zbiorów reprezentantów oraz algebraiczne podejście Cut&Count. Jako zbioru testowego użyliśmy instancji z FHCP Challange.W drugiej części pracy sprawdzamy, czy kernel dla problemu OCT stworzony przez S. Kratscha oraz M. Wahlströma mógłby zostać użyty jako algorytm preprocessingu w problemach pochodzących ze świata rzeczywistego. Naszą implementację opartą o tę kernelizację testujemy zarówno na klasycznych jak i nowych zbiorach instancji zebranych w tegorocznej pracy Goodricha i in. i porównujemy nasze wyniki z wynikami preprocessingu wykorzystanego w tejże pracy.Over the last decade many new parameterized and kernelization algorithms have emerged. As in thereal world problems some parameters are often small, such algorithms are likely to be useful for dealingwith them. For this reason in recent years we can observe an increasing interest in their experimentalevaluation evident in a range of appearing papers on this matter.This thesis is a summary of my participation in the project “Recent trends in kernelization: theory andexperimental evaluation”. Following the trends, we experimentally evaluate some programs based on thenew FPT approaches, especially those using representative sets. We also provide code repositories withall of our implementations needed to reproduce the results.In the first part we evaluate a few approaches for finding Hamiltonian Cycle on graphs with smalltreewidth using a given tree decomposition. We compare a naive approach with two approaches usingrepresentative sets and algebraic Cut&Count approach. As a benchmark we use a dataset from FlindersHamiltonian Cycle Project Challenge.In the second part we check if the kernel for the Odd Cycle Transversal problem developed by Kratschet al. could be used as a preprocessing algorithm for real world instances. We evaluate our implementationof it on both classical Wernicke-Hüffner and new Beasley and GKA datasets and compare our results tothose of the preprocessing routines used by Goodrich et al. in their recent experimental paper