Parameterized Inapproximability of Target Set Selection and Generalizations
From MaRDI portal
Publication:5175620
DOI10.3233/COM-140030zbMath1320.68088MaRDI QIDQ5175620
Florian Sikora, André Nichterlein, Morgan Chopin, Cristina Bazgan
Publication date: 24 February 2015
Published in: Computability (Search for Journal in Brave)
Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
A parameterized complexity view on collapsing \(k\)-cores ⋮ Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available ⋮ Target set selection with maximum activation time ⋮ Domination and convexity problems in the target set selection model ⋮ Unnamed Item ⋮ Target set selection for conservative populations ⋮ The complexity of finding effectors ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Target set selection parameterized by vertex cover and more ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ On reconfigurability of target sets
This page was built for publication: Parameterized Inapproximability of Target Set Selection and Generalizations
