Parameterized complexity of weighted target set selection

DOI10.1016/J.TCS.2025.115414MaRDI QIDQ6949547zbMATH OpenFDO

Authors Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou

Publication date 1 August 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115414

zbMATH Keywords

graph algorithmsparameterized complexitytarget-set selection

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• A 2k kernel for the cluster editing problem
• A faster algorithm for vertex cover parameterized by solution size
• A single-exponential time 2-approximation algorithm for treewidth
• Complexity of Finding Embeddings in a k-Tree
• Constant thresholds can make target set selection tractable
• Even faster parameterized cluster deletion and cluster editing
• Fast FPT-approximation of branchwidth
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph Classes: A Survey
• Introduction to algorithms.
• Latency-bounded target set selection in social networks
• Modular decomposition and transitive orientation
• Nondeterminism within $P^ * $
• On the approximability of influence in social networks
• Parameterized algorithms
• Parameterized approximability of maximizing the spread of influence in networks
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Some results on the target set selection problem
• Target Set Selection in Dense Graph Classes
• Target set selection parameterized by clique-width and maximum threshold
• Target set selection parameterized by vertex cover and more
• Treewidth governs the complexity of target set selection
• Weighted target set selection on trees and cycles

This page was built for publication: Parameterized complexity of weighted target set selection

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