5 papers
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant such tha…
Parameterized Inapproximability Hypothesis under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the numb…
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…
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…
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…