On the Parameterized Complexity of Approximating Dominating Set

DOI10.1145/3325116zbMath1473.68099OpenAlexW2968783941WikidataQ127362945 ScholiaQ127362945MaRDI QIDQ5215462

Bundit Laekhanukit, Pasin Manurangsi, C. S. Karthik

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3325116

zbMATH Keywords

dominating setset coverparameterized inapproximability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (10)

The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ A note on hardness of computing recursive teaching dimension ⋮ Recognizing when a preference system is close to admitting a master list ⋮ How to find a good explanation for clustering? ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Tight FPT approximation for socially fair clustering ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Approximation and hardness of shift-Bribery ⋮ Unnamed Item ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

This page was built for publication: On the Parameterized Complexity of Approximating Dominating Set