Using matroids in algorithms

Matroids are mathematical structures that can be used to analize many combinatorial problems. Especially useful are matroids known as linear matroids, which can be represented by matrices. They can be used to design polynomial compression algorithms for some FPT problems. This work presents commonly used matroid classes and describes an implemented by me library which allows to represent linear matroids and perform operations on them along with examples of its usage in kernelization algorithms for problems Odd Cycle Transversal, Almost-2-SAT, d-Hitting Set and d-SetPacking.

Matroidy są strukturą matematyczną wykorzystywaną do analizy wielu problemów kombinatorycznych. Szczególnie przydatne okazują się tak zwane matroidy liniowe, które można reprezentować w postaci macierzy. Za ich pomocą możemy stworzyć algorytmy wielomianowej kompresji dla niektórych problemów z klasy FPT. Celem pracy jest przedstawienie najczęściej wykorzystywanych klas matroidów oraz opisanie zaimplementowanej przeze mnie biblioteki w języku C++ umożliwiającej reprezentację matroidów liniowych oraz operowanie na nich wraz z przykładami jej użycia do kernelizacji problemów Odd Cycle Transversal, Almost-2-SAT, d-Hitting Set oraz d-SetPacking.