A Framework for Parameterized Hardness of Approximation

In this talk we will see a framework to show inapproximability of parameterized problems. This framework generalizes the 'Distributed PCPs' framework recently introduced by Abboud et al. [FOCS'17]. By applying the gadget reductions given by Chalermsook et al. [FOCS'17] to this framework, we settle the inapproximability of parameterized dominating set under various time hypotheses.

Joint work with Bundit Laekhanukit and Pasin Manurangsi.

Preprint available at https://eccc.weizmann.ac.il/report/2017/186/