37 citations · 43 across the 12 of their papers we have counts for
17 papers
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
Rishav Gupta, Bingkai Lin, Xin Zheng
We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (), yields tight lower bounds for approximating the parameterized Maximum…
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…
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
Shuangle Li, Bingkai Lin, Yuwei Liu
In this paper we present a new gap-creating randomized self-reduction for parameterized Maximum Likelihood Decoding problem over (-MLD). The reduction takes a…
FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
Huairui Chu, Bingkai Lin
Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are pr…
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…
Constant Approximating k-Clique is W[1]-hard
Bingkai Lin
For every graph , let be the largest size of complete subgraph in . This paper presents a simple algorithm which, on input a graph , a positive integer and a sm…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
A Simple Gap-producing Reduction for the Parameterized Set Cover Problem
Bingkai Lin
Given an -vertex bipartite graph , the goal of set cover problem is to find a minimum sized subset of such that every vertex in is adjacent to some vertex of…
The Hardness of Embedding Grids and Walls
Yijia Chen, Martin Grohe, Bingkai Lin
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph from some class of "pattern graphs" can be embedd…
Fixed-parameter Approximability of Boolean MinCSPs
Édouard Bonnet, László Egri, Bingkai Lin +1
The minimum unsatisfiability version of a constraint satisfaction problem (MinCSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equiva…
The Constant Inapproximability of the Parameterized Dominating Set Problem
Yijia Chen, 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 aut…
The Parameterized Complexity of k-Biclique
Bingkai Lin
Given a graph and a parameter , the -biclique problem asks whether contains a complete bipartite subgraph . This is the most easily stated problem on graphs…
The parameterized complexity of k-edge induced subgraphs
Bingkai Lin, Yijia Chen
We prove that finding a -edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial ob…