We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. Answering a long-standing open question, we show that, under standard conjectures, there is no FTP approximation algorithm for the maximum clique problem and the minimum dominating set problem.
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more
Trevisan, Luca
2020
Abstract
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. Answering a long-standing open question, we show that, under standard conjectures, there is no FTP approximation algorithm for the maximum clique problem and the minimum dominating set problem.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
