Leírás
A cikkben a paraméteres lefogó csúcshalmaz problémát (parametrized VERTEX
COVER) vizsgálják meg, ahol a paraméter az optimális egész megoldás és az LP
relaxált megoldása közötti különbség. Az addigi legjobb előfeldolgozási
szabályokkal és branching lépésekkel működő O^*(2.618^k) algoritmust tudták
megjavítani. Szofisztikáltabb branching lépésekkel sikerült O^*(2.3146^k)
algoritmust megadniuk.
Ezt az eredményt felhasználva korábbi és új visszavezetésekkel
$O^*(2.3146^k)$ algoritmust adnak a paraméteres ABOVE
GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION, és
ALMOST 2-SAT problémákra, valamint $O^*(1.5214^k)$ lépésszámút a KÖNIG
VERTEX DELETION és a legkisebb odd cycle transversal, illetve König csúcs
törlési halmaz méretével paraméterezett VERTEX COVER problémákra. Ezek az
algoritmusok jelentősen javítják meg az addig ismert lépésszámokat.
Végül pedig egy egyszerű kernel konstrukció kerül bemutatásra, amely
legfeljebb 2k-c\log k csúcsot használ az általánosan paraméterezett VERTEX
COVER problémára.