Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333865 | Theoretical Computer Science | 2016 | 21 Pages |
Abstract
Recent papers investigated the maximum infection time tP3(G) of the P3-convexity (also called maximum time of 2-neighbor bootstrap percolation) and the maximum infection time tmo(G) of the monophonic convexity. In 2014, it was proved that, for bipartite graphs, deciding whether tP3(G)â¥k is polynomial time solvable for kâ¤4, but is NP-complete for kâ¥5[23]. In 2015, it was proved that deciding whether tmo(G)â¥2 is NP-complete even for bipartite graphs [12]. In this paper, we investigate the maximum infection time tgd(G) of the geodesic convexity. We prove that deciding whether tgd(G)â¥k is polynomial time solvable for k=1, but is NP-complete for kâ¥2 even for bipartite graphs. We also present an O(n3m)-time algorithm to determine tgd(G) and tmo(G) in distance-hereditary graphs. For this, we characterize all minimal hull sets of a general graph in the monophonic convexity. Moreover, we improve the complexity of the fastest known algorithm for finding a minimum hull set of a general graph in the monophonic convexity.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
FabrÃcio Benevides, Victor Campos, Mitre C. Dourado, Rudini M. Sampaio, Ana Silva,