8 citations · 30 across the 29 of their papers we have counts for
4 papers · 1 filter
Independent set in -Claw-Free Graphs: Conditional -boundedness and the Power of LP/SDP Relaxations
Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi +1
This paper studies -claw-free graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximum-weight i…
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…