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

DOI10.1016/J.IPL.2017.12.006zbMATH Open1427.68127OpenAlexW2780415142MaRDI QIDQ1705656FDOQ1705656

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

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

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)

Cites Work

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

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)