We give an algorithm that finds a zero forcing set which approximates the optimal size by a factor of pw ( G ) + 1 , where pw ( G ) is the pathwidth of G . The algorithm requires a path decomposition of G , and given this it runs in O ( n m ) time, where n and m are the order and size of the graph, respectively. This is the first zero forcing algorithm with a guarantee on both the approximation ratio and on the run-time. As a corollary, we obtain a new upper bound on the zero forcing number in terms of the fort number and the pathwidth. The algorithm is based on a correspondence between zero forcing sets and forcing arc sets. This correspondence leads to a new bound on the zero forcing number in terms of vertex cuts, and to new, short proofs for known bounds on the zero forcing number.

Abstract Various models to quantify the reliability of a network have been studied where certain components of the graph may fail at random and the probability that the remaining graph is connected is the proxy for reliability. We introduce a strengthening of one of these models by considering the probability that the remaining graph is cop‐win. A graph is cop‐win if one cop can win the game Cops and Robber. More precisely, for a graph G with nodes that are operational independently with probability p, the node cop‐win reliability of G, denoted , is the probability that the operational nodes induce a cop‐win subgraph of G. It is then of interest to find graphs G with n nodes and m edges such that for all p ∈ [0, 1] and all graphs H with n nodes and m edges. We show that such graphs exist among unicyclic and bicyclic graphs, respectively.