{"id":"arxiv/2605.10526","url":"https://arxiv.org/abs/2605.10526","tags":["math.OC","cs.DM"],"score":0,"title":"Randomized Max-Vertex-Coverage Interdiction under Matroid Constraints","domain":"math.OC","source":"arxiv","authors":["Changjun Wang","Chenhao Wang"],"reviews":0,"subject":"math.OC","summary":"We study a class of bilevel interdiction problems in which the follower's optimization problem is computationally intractable. Motivated by network defense applications, we introduce the Randomized Max-Vertex-Coverage Interdiction (RMVCI) problem under matroid constraints. In this zero-sum Stackelberg game, the leader commits to a randomized interdiction strategy over feasible vertex subsets, while the follower, after observing the induced protection probabilities, chooses a matroid-constrained attack to maximize the expected coverage of network edges. The main challenge stems from the fact…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}