39 citations · 308 across the 129 of their papers we have counts for
4 papers · 2 filters
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…
Inapproximability of VC Dimension and Littlestone's Dimension
Pasin Manurangsi, Aviad Rubinstein
We study the complexity of computing the VC Dimension and Littlestone's Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x…
Inapproximability of Maximum Biclique Problems, Minimum -Cut and Densest At-Least--Subgraph from the Small Set Expansion Hypothesis
Pasin Manurangsi
The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose edge expansio…