vix.ing · top · new · best · stats · spec

A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More

2021/12/09 by Ren, Xuandi
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2112.04669

Abstract

In the past a few years, many interesting inapproximability results have been obtained from the parameterized perspective. This article surveys some of such results, with a focus on k-Clique, k-SetCover, and other related problems.

Related