Dynamic monopolies for interval graphs with bounded thresholds

DOI10.1016/J.DAM.2019.01.022MaRDI QIDQ1741518zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Bessy, Stefan Ehard, Lucia Draque Penso, Dieter Rautenbach

Publication date 3 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

target set selectioninterval graphdynamic monopoly

Mathematics Subject Classification ID

Dynamic programming (90C39) Connectivity (05C40) Graph theory (05C99)

Abstract: For a graph $G$ and an integer-valued threshold function $au$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $au(u)$ neighbors in it eventually yields the vertex set of $G$. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.

Recommendations

• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On dynamic monopolies of graphs: the average and strict majority thresholds
• On dynamic monopolies of graphs with general thresholds
• Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
• On monopoly and dynamic monopoly of Cartesian product of graphs with constant thresholds.

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Constant thresholds can make target set selection tractable
• Irreversible 2-conversion set in graphs of bounded degree
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• On the approximability of influence in social networks
• On the clique-width of some perfect graph classes
• Some results on the target set selection problem
• Target set selection parameterized by clique-width and maximum threshold
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth governs the complexity of target set selection

Cited in

(14)

• On reconfigurability of target sets
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• On monopoly and dynamic monopoly of Cartesian product of graphs with constant thresholds.
• On some tractable and hard instances for partial incentives and target set selection
• Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
• Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
• On the complexity of target set selection in simple geometric networks
• Partial immunization of trees
• Establishing herd immunity is hard even in simple geometric networks
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Vaccinate your trees!
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• Target set selection with maximum activation time
• Integer programming approach to static monopolies in graphs

This page was built for publication: Dynamic monopolies for interval graphs with bounded thresholds

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