The P3 infection time is W[1]-hard parameterized by the treewidth

DOI10.1016/J.IPL.2017.12.006MaRDI QIDQ1705656zbMATH OpenOpenAlexFDO

Authors Thiago Marcilon, Rudini M. 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

zbMATH Keywords

computational complexitytreewidthfixed parameter tractabilityinfection time\(P_3\) convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• The infection time of graphs
• On the vertex cover \(P_3\) problem parameterized by treewidth
• Fixed-parameter tractability of treewidth and pathwidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Inapproximability of treewidth and related problems
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• Bootstrap percolation in living neural networks
• Complexity results related to monophonic convexity
• Diffusion in Social Networks
• Graph minors. III. Planar tree-width
• Growth rates and explosions in sandpiles
• Inapproximability results related to monophonic convexity
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Lower bounds based on the exponential time hypothesis
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• On the complexity of \(k\)-SAT
• On the complexity of some colorful problems parameterized by treewidth
• On the parameterized complexity of multiple-interval graph problems
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The maximum infection time in the geodesic and monophonic convexities
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(4)

• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Bounds and algorithms for geodetic hulls
• The maximum infection time in the geodesic and monophonic convexities
• Target set selection with maximum activation time

This page was built for publication: The P3 infection time is W[1]-hard parameterized by the treewidth

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