The P3 infection time is W[1]-hard parameterized by the treewidth
From MaRDI portal
Publication:1705656
DOI10.1016/j.ipl.2017.12.006zbMath1427.68127OpenAlexW2780415142MaRDI QIDQ1705656
Thiago Marcilon, Rudini Menezes Sampaio
Publication date: 16 March 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2017.12.006
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- On slowly percolating sets of minimal size in bootstrap percolation
- Inapproximability results related to monophonic convexity
- Bootstrap percolation in living neural networks
- On the complexity of some colorful problems parameterized by treewidth
- Graph minors. III. Planar tree-width
- The maximum infection time in the geodesic and monophonic convexities
- Growth rates and explosions in sandpiles
- Complexity results related to monophonic convexity
- On the parameterized complexity of multiple-interval graph problems
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
- The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
- Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
- Diffusion in Social Networks
- The sharp threshold for bootstrap percolation in all dimensions
- On the complexity of \(k\)-SAT
