3 papers
cs.CC2023
Improved Hardness of Approximating k-Clique under ETH
Bingkai Lin, Xuandi Ren, Yican Sun +1
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no -time algorithm that can decide whether an -vertex gr…
cs.DS2022
Constant Approximating Parameterized -SetCover is W[2]-hard
Bingkai Lin, Xuandi Ren, Yican Sun +1
In this paper, we prove that it is W[2]-hard to approximate k-SetCover within any constant ratio. Our proof is built upon the recently developed threshold graph composition techniq…
cs.CC2021
On Lower Bounds of Approximating Parameterized -Clique
Bingkai Lin, Xuandi Ren, Yican Sun +1
Given a simple graph and an integer , the goal of -Clique problem is to decide if contains a complete subgraph of size . We say an algorithm approximates -Cliqu…