Bingkai Lin

TCS Journal 2026 Journal Article

Hardness and fixed parameter tractability for pinwheel scheduling problems

• Yusuke Kobayashi
• Bingkai Lin
• Joseph Swernofsky

In the Pinwheel Packing problem, we are given a set of recurring tasks, each associated with a positive integer ai for task i. The objective is to select one task to perform each day such that every task i is performed at least once within every ai consecutive days. The exact computational complexity of this problem, where ∑ 1 / a i = 1, has remained an open question for more than 30 years; in particular, it is still unknown whether the problem is NP -hard. The first contribution of this paper is to show that Pinwheel Packing cannot be solved in polynomial time under a standard complexity assumption, improving upon the hardness result shown by Jacobs and Longo. Additionally, we present fixed-parameter algorithms for variants of Pinwheel Packing, parameterized by the number of tasks.

STOC Conference 2025 Conference Paper

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

• Venkatesan Guruswami
• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Kewen Wu 0001

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f :ℕ→ℕ, no f ( k )· n O (1) -time algorithm can, on input a k -variable CSP instance with domain size n , find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires n k 1− o (1) time. This immediately implies, for example, that finding a ( k /2)-clique in an n -vertex graph with a k -clique requires n k 1− o (1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k -ExactCover and Max k -Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing.

STOC Conference 2024 Conference Paper

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

• Venkatesan Guruswami
• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Kewen Wu 0001

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

SODA Conference 2023 Conference Paper

Constant Approximating Parameterized k -SETCOVER is W[2]-hard

• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Xiuhan Wang

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 technique. We propose a strong notion of threshold graphs and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time ratio approximation algorithms for the non-parameterized k -SETCOVER problem with k as small as, assuming W[1] ≠ FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.

FOCS Conference 2023 Conference Paper

Improved Hardness of Approximating k-Clique under ETH

• Bingkai Lin
• Xuandi Ren
• Yican Sun
• Xiuhan Wang

In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k) \cdot n^{k^{o(1 / \log \log k)}}$-time algorithm that can decide whether an n-vertex graph contains a clique of size k or contains no clique of size $k / 2$, and no FPT algorithm can decide whether an input graph has a clique of size k or no clique of size $k / f(k)$, where $f(k)$ is some function in $k^{1-o(1)}$. Our results significantly improve the previous works [1], [2]. The crux of our proof is a framework to construct gap-producing reductions for the k-CLIQUE problem. More precisely, we show that given an error-correcting code $C: \Sigma_{1}^{k} \rightarrow \Sigma_{2}^{k^{\prime}}$ that is locally testable and smooth locally decodable in the parallel setting, one can construct a reduction which on input a graph G outputs a graph $G^{\prime}$ in $\left(k^{\prime}\right)^{O(1)} \cdot n^{O\left(\log \left|\Sigma_{2}\right| / \log \left|\Sigma_{1}\right|\right)}$ time such•if G has a clique of size k, then $G^{\prime}$ has a clique of size K, where $K=\left(k^{\prime}\right)^{O(1)}$. •if G has no clique of size k, then $G^{\prime}$ has no clique of size $(1-\varepsilon) \cdot K$ for some constant $\varepsilon \in(0, 1)$. We then construct such a code with $k^{\prime}=k^{\Theta(\log \log k)}$ and $\left|\Sigma_{2}\right|=\left|\Sigma_{1}\right|^{k^{0. 54}}$, establishing the hardness result above. Our code generalizes the derivative code [3] into the case with a super constant order of derivatives.

STOC Conference 2021 Conference Paper

Constant approximating k-clique is w[1]-hard

• Bingkai Lin

For every graph G , let ω( G ) be the largest size of complete subgraph in G . This paper presents a simple algorithm which, on input a graph G , a positive integer k and a small constant є>0, outputs a graph G ′ and an integer k ′ in 2 Θ( k 5 ) · | G | O (1) -time such that (1) k ′≤ 2 Θ( k 5 ) , (2) if ω( G )≥ k , then ω( G ′)≥ k ′, (3) if ω( G )< k , then ω( G ′)< (1−є) k ′. This implies that no f ( k )· | G | O (1) -time algorithm can distinguish between the cases ω( G )≥ k and ω( G )< k / c for any constant c ≥ 1 and computable function f , unless FPT = W [1].

SODA Conference 2020 Conference Paper

A nearly 5/3-approximation FPT Algorithm for Min- k -Cut

• Ken-ichi Kawarabayashi
• Bingkai Lin

Given an edged-weighted graph G, the min- k -cut problem asks for a set of edges with minimum total weight whose removal breaks the graph G into at least k connected components. It is well-known that the greedy algorithm can find a (2 – 2/ k )-approximation of the min- k -cut in polynomial time. Assuming the Small Set Expansion Hypothesis (SSEH), no polynomial time algorithm can achieve an approximation ratio better than two [9]. Recently, Gupta, Lee and Li [5] gave a 1. 9997-approximation FPT algorithm for the min- k -cut parameterized by k. They also improved this approximation ratio to 1. 81 [4]. We generalize their proof techniques and show that the min- k -cut has a nearly 5/3-approximation FPT algorithm. Our proof is self-contained and much shorter than that of Gupta, Lee and Li.

I&C Journal 2017 Journal Article

The parameterized complexity of k-edge induced subgraphs

• Bingkai Lin
• Yijia Chen

We prove that finding a k-edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial observations, Gauss' famous Eureka theorem, and a generalization of the well-known fpt-algorithm for the model-checking problem for first-order logic on graphs with locally bounded tree-width due to Frick and Grohe. On the other hand, we show that two natural counting versions of the problem are hard. Hence, the k-edge induced subgraph problem is one of the very few known examples in parameterized complexity that are easy for decision while hard for counting.

FOCS Conference 2016 Conference Paper

The Constant Inapproximability of the Parameterized Dominating Set Problem

• Yijia Chen 0001
• Bingkai Lin

We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT = W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem [25]. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis.

SODA Conference 2015 Conference Paper

The Parameterized Complexity of k -Biclique

• Bingkai Lin