Bingkai Lin

activity

20172021

collaborators

4 papers

cs.CC2021

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 sm…

cs.CC2019

Parameterized Intractability of Even Set and Shortest Vector Problem

Arnab Bhattacharyya, Édouard Bonnet, László Egri +5

The $k$ -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $F_{2}$ , which can be stated as follows: given a generator matrix $\m…

cs.CC2019

A Simple Gap-producing Reduction for the Parameterized Set Cover Problem

Bingkai Lin

Given an $n$ -vertex bipartite graph $I = (S, U, E)$ , the goal of set cover problem is to find a minimum sized subset of $S$ such that every vertex in $U$ is adjacent to some vertex of…

cs.CC2017

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 $G$ from some class $K$ of "pattern graphs" can be embedd…