FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set

Huairui Chu, Bingkai Lin

Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are pr…