I detta papper föreslår vi en algoritm som, med tanke på en oriktad graf G av m kanter och ett heltal k, beräknar en graf G och ett heltal k i O(k 4 m) tid sådan att (1) storleken på grafen G är O(k 2 ), (2) k ≤ k, och (3) G har en feedback vertex uppsättning storlek som mest k om och endast om G har en feedback vertex uppsättning storlek på de flesta k. Detta är den första linjära tiden polynom-storlek kärna för Feedback Vertex Set. Storleken på vår kärna är 2k 2 + k hörn och 4k 2 kanter, som är mindre än den tidigare bästa av 4k 2 hörn och 8k 2 kanter. Således förbättrar vi storleken och körtiden samtidigt. Vi noterar att Feedback Vertex Set inte tillåter en O(k 2-) storlekskärna för någon > 0 under antagandet av NP  på coNP/poly. Vår kärna utnyttjar k-submodulär avkoppling, vilket är en nyutvecklad teknik för att erhålla effektiva FPT-algoritmer för olika problem. Den dubbla k-submodulära avslappningen av Feedback Vertex Set kan ses som en halv-integrerad variant av A-pat packning, och för att få linjär-tid komplexitet, föreslår vi en effektiv förstärkning-pat algoritm för detta problem. Vi tror att denna kombinatoriska algoritm är av oberoende intresse. En lösare baserad på den föreslagna metoden vann första plats i den 1: a Parameterized algoritmer och beräkningsexperiment (PACE) utmaning.
Ett annat specialfall av F-förpackningsproblemet är LP för FVS, för vilket Iwata REF erhöll en O (km)-tid förstärkning-pat algoritm.
Linear-time Kernelization for Feedback Vertex Set
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}