Showing cs.CCShow all
2 papers · 1 filter
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.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…