Target set selection parameterized by clique-width and maximum threshold

DOI10.1007/978-3-319-73117-9_10MaRDI QIDQ5127178zbMATH OpenOpenAlexFDO

Authors Tim A. Hartmann

Publication date 21 October 2020

Published in SOFSEM 2018: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: The Target Set Selection problem takes as an input a graph $G$ and a non-negative integer threshold $mboxthr(v)$ for every vertex $v$. A vertex $v$ can get active as soon as at least $mboxthr(v)$ of its neighbors have been activated. The objective is to select a smallest possible initial set of vertices, the target set, whose activation eventually leads to the activation of all vertices in the graph. We show that Target Set Selection is in FPT when parameterized with the combined parameters clique-width of the graph and the maximum threshold value. This generalizes all previous FPT-membership results for the parameterization by maximum threshold, and thereby solves an open question from the literature. We stress that the time complexity of our algorithm is surprisingly well-behaved and grows only single-exponentially in the parameters.

Recommendations

• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Parameterized inapproximability of target set selection and generalizations
• Parameterized inapproximability of target set selection and generalizations
• Treewidth governs the complexity of target set selection

Cited in

(17)

• Dynamic monopolies for interval graphs with bounded thresholds
• On some tractable and hard instances for partial incentives and target set selection
• Target set selection parameterized by vertex cover and more
• Constant thresholds can make target set selection tractable
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Treewidth governs the complexity of target set selection
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Target Set Selection in Dense Graph Classes
• Target set selection in dense graph classes
• Target set selection problem for honeycomb networks
• Establishing herd immunity is hard even in simple geometric networks
• Target set selection with maximum activation time
• On the complexity of target set selection in simple geometric networks
• Parameterized complexity of weighted target set selection
• Parameterized complexity of weighted target set selection
• Balancing the spread of two opinions in sparse social networks
• A parameterized complexity view on collapsing \(k\)-cores

This page was built for publication: Target set selection parameterized by clique-width and maximum threshold

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