Parameterized inapproximability of target set selection and generalizations

DOI10.1007/978-3-319-08019-2_2MaRDI QIDQ5175873zbMATH OpenOpenAlexFDO

Authors Morgan Chopin, André Nichterlein, Florian Sikora, Cristina Bazgan

Publication date 25 February 2015

Published in Language, Life, Limits (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3565

Mathematics Subject Classification ID

Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to "activate" s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex $v$ is activated during the propagation process if at least $thr(v)$ of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions $f$ and $ho$ this problem cannot be approximated within a factor of $ho(k)$ in $f(k)cdot{n}^{O(1)}$ time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimization versions of the problem for which we prove similar hardness results.

Recommendations

• Parameterized inapproximability of target set selection and generalizations
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• On approximating target set selection
• Constant thresholds can make target set selection tractable

Cited in

(14)

• Some results on the target set selection problem
• Parameterized approximability of maximizing the spread of influence in networks
• The complexity of finding harmless individuals in social networks
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Domination and convexity problems in the target set selection model
• The robust set problem: parameterized complexity and approximation
• Combinatorial model and bounds for target set selection
• On approximating target set selection
• Constant thresholds can make target set selection tractable
• Parameterized approximability of maximizing the spread of influence in networks
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Target set selection in dense graph classes
• Target set selection parameterized by clique-width and maximum threshold
• Parameterized inapproximability of target set selection and generalizations

This page was built for publication: Parameterized inapproximability of target set selection and generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175873)