Algorithm for solving the attack and interception game on networks

The paper "Attack and interception in networks" (F. Bloch, K. Chatterjee, B. Dutta, 2022), describes a game where a single attacker chooses a target and a path and each node chooses a level of protection. Main results proposed in this paper are the existence and uniqueness of NE of the proposed game and the characterization of NE when the set of nodes attacked with positive probability is known. Following this  paper, we propose a polynomial (with respect to the number of players) time algorithm for finding the set of attacked nodes. This algorithm allows us to find the NE of the described game in polynomial time.