16 citations · 59 across the 25 of their papers we have counts for
6 papers · 1 filter
Simple Combinatorial Construction of the -Lower Bound for Approximating the Parameterized -Clique
Yijia Chen, Yi Feng, Bundit Laekhanukit +1
In the parameterized -clique problem, or -Clique for short, we are given a graph and a parameter . The goal is to decide whether there exist vertices in t…
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
We study the parameterized complexity of approximating the -Dominating Set (DomSet) problem where an integer and a graph on vertices are given as input, and the goal…
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
The study of graph products is a major research topic and typically concerns the term , e.g., to show that . In this paper, we study graph products in a no…
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the maximum…
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
Bundit Laekhanukit
Optimizing parameters of Two-Prover-One-Round Game (2P1R) is an important task in PCPs literature as it would imply a smaller PCP with the same or stronger soundness. While this is…