Király Zoltán: Néhány alapvető fix paraméteres technika

Néhány nem túl régi, de mégis ma már klasszikus eredményről lesz szó.
3 feladatról beszélünk.

Az első a VERTEX COVER ABOVE LP, ahol az a kérdés, hogy egy
gráf éleit le lehet-e fogni az optimális törtlefogásnál maximum k-val több
csúccsal.

Második az ODD CYCLE TRANSVERSAL, ahol az a kérdés, hogy ki lehet-e törölni
egy gráfból k csúcsot, hogy a maradék páros gráf legyen.

A harmadik az EDGE MULTIWAY CUT, ahol egy (irányítatlan) gráf mellett adott
még egy T terminálhalmaz, és az a kérdés, hogy ki lehet-e törölni k élet úgy,
hogy minden komponensbe maximum 1 terminál kerüljön.