Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:

$FPT = XPuniform\implies EPTAS = PTAS$.

Fundamentals of Parametrized complexity on page $534$ has

enter image description here

which from "we will only look at XP and remark that all the results hold with no change for uniform XP as well. By standard diagonalization, we have the following basic result:

Proposition $27.3.1$. FPT is a proper subset of XP."

means $FPT$ is a proper subset of $XP_{uniform}$ as well.

  1. Is this correct information? If so this result has been known for a long time. So is there any updates that need to be made to complexity zoo section https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas and is there any consequences to approximation algorithms because of this?

  2. Does $FPT=W[P]$ have any consequences to approximation algorithms? I see only reverse consequences in complexity zoo:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.