Source author record

Bingkai Lin

Bingkai Lin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

What is connected

4works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

On Lower Bounds of Approximating Parameterized $k$-Clique

Given a simple graph $G$ and an integer $k$, the goal of $k$-Clique problem is to decide if $G$ contains a complete subgraph of size $k$. We say an algorithm approximates $k$-Clique within a factor $g(k)$ if it can find a clique of size at least $k / g(k)$ when $G$ is guaranteed to have a $k$-clique. Recently, it was shown that approximating $k$-Clique within a constant factor is W[1]-hard [Lin21]. We study the approximation of $k$-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Lin21] already implies an $n^{Ω(\sqrt[6]{\log k})}$-time lower bound under ETH. We improve this lower bound to $n^{Ω(\log k)}$. Using the gap-amplification technique by expander graphs, we also prove that there is no $k^{o(1)}$ factor FPT-approximation algorithm for $k$-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no $n^{O(\frac{k}{\log k})}$ algorithm to approximate $k$-Clique within a constant factor, then PIH is true.

preprint2021arXiv

Constant Approximating k-Clique is W[1]-hard

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)}\cdot |G|^{O(1)}$-time such that (1) $k'\le 2^{Θ(k^5)}$, (2) if $ω(G)\ge k$, then $ω(G')\ge k'$, (3) if $ω(G)<k$, then $ω(G')< (1-ε)k'$. This implies that no $f(k)\cdot |G|^{O(1)}$-time algorithm can distinguish between the cases $ω(G)\ge k$ and $ω(G)<k/c$ for any constant $c\ge 1$ and computable function $f$, unless $FPT= W[1]$.

preprint2015arXiv

The Constant Inapproximability of the Parameterized Dominating Set Problem

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. 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.

preprint2012arXiv

The parameterized complexity of k-edge induced subgraphs

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 \emph{Eureka} theorem [Andrews, 86], 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 [Frick and Grohe, 01]. 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 rare known examples in parameterized complexity that are easy for decision while hard for counting.