Leírás
Az előadáson Marx Dániel "A parameterized view on matroid optimization
problems" c. cikke alapján megmutatjuk néhány matroid műveletről, hogy azok
randomizált polinom időben elvégezhetők, azaz ha adott egy M matroid a
lineáris reprezentációjával, akkor a művelet végrehajtása után kapott M'
matroid reprezentációja polinom időben megkonstruálható, ahol a hiba
valószínűsége tetszőlegesen kicsinek is választható.
Ezen eredmények következményeként randomizált FPT-algoritmust adunk az
l-MATROID_INTERSECTION problémára. A fentiekre támaszkodva Kratsch és
Wahlström k^4.5 méretű randomizált polinomiális kernelt gyártottak az OCT
problémára a "Compression via Matroids: A Randomized Polynomial Kernel for Odd
Cycle Transversal" c. cikkben: ezen keresztül fogjuk áttekinteni a gammoidok
segítségével történő elkódolást és a Reed-Smith-Vetta-algoritmust is használó
kernelizációt.