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

Recent papers investigated the maximum infection times tP3(G), tgd(G) and tmo(G) of the P3 convexity, geodesic convexity and monophonic convexity, respectively. In [4] and [8], it was proved that deciding whether tgd(G)≥2 or tmo(G)≥2 are NP-Complete problems even for bipartite graphs. In [17], it wa...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2018-04, Vol.132, p.55-61
Main Authors: Marcilon, Thiago, Sampaio, Rudini
Format: Article
Language:English
Subjects:
[formula omitted] convexity
Computational complexity
Fixed parameter tractability
Infection time
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent papers investigated the maximum infection times tP3(G), tgd(G) and tmo(G) of the P3 convexity, geodesic convexity and monophonic convexity, respectively. In [4] and [8], it was proved that deciding whether tgd(G)≥2 or tmo(G)≥2 are NP-Complete problems even for bipartite graphs. In [17], it was proved that, in bipartite graphs, deciding whether tP3(G)≥k is polynomial time solvable for k≤4, but is NP-Complete for k≥5. In this paper, we prove that the P3 infection time problem is fixed parameter tractable parameterized by treewidth + k, but is W[1]-hard when parameterized only by the treewidth. •P3 infection time is the maximum number of rounds needed to infect all vertices of a graph according to the P3 infection.•P3 infection time problem is W[1]-hard on the treewidth of the graph.•P3 infection time problem is fixed parameter tractable on the treewidth, if the time is fixed.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2017.12.006