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.
2020
Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4033667
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 6
social impact