Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

DOI10.1007/s00453-007-9148-9zbMath1170.68019MaRDI QIDQ958211

Saket Saurabh, Venkatesh Raman

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9148-9

zbMATH Keywords

independent set; dominating set; set cover; parameterized complexity; \(t\)-vertex cover

Mathematics Subject Classification ID

05C38: Paths and cycles

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)