research
∙
04/06/2023
Improved Hardness of Approximating k-Clique under ETH
In this paper, we prove that assuming the exponential time hypothesis (E...
share
research
∙
02/09/2022
Constant Approximating Parameterized k-SetCover is W[2]-hard
In this paper, we prove that it is W[2]-hard to approximate k-SetCover w...
research
∙
11/28/2021
On Lower Bounds of Approximating Parameterized k-Clique
Given a simple graph G and an integer k, the goal of k-Clique problem is...
research
∙
02/09/2021
Constant Approximating k-Clique is W[1]-hard
For every graph G, let ω(G) be the largest size of complete subgraph in ...
research
∙
09/04/2019
Parameterized Intractability of Even Set and Shortest Vector Problem
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
02/11/2019