arxiv: 2605.10526 · v1 · submitted 2026-05-11 · 🧮 math.OC · cs.DM

Recognition: no theorem link

Randomized Max-Vertex-Cover Interdiction with Matroid Constraints

Changjun Wang, Chenhao Wang

Pith reviewed 2026-05-12 04:55 UTC · model grok-4.3

classification 🧮 math.OC cs.DM

keywords bilevel optimizationapproximation algorithmsmatroid constraintsvertex cover interdictionStackelberg gamesrandomized strategiesnetwork interdictionlinear programming relaxation

0 comments

The pith

An 8/3-approximation algorithm computes randomized protection strategies for matroid-constrained max-vertex-cover interdiction.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a bilevel model for a Stackelberg game in which a leader randomly protects vertices under matroid constraints to minimize the expected weight of edges attacked by an unprotected follower set. Because the follower's max-vertex-cover problem is NP-hard, the authors relax it to a linear program whose integrality gap is exactly 4/3. They then replace the follower with this LP inside the bilevel program, shift the leader's strategy from distributions over sets to distributions over vertices, and invoke a general approximation framework for bilevel interdiction problems to obtain a 2-approximation on the relaxed instance. Composing the factors produces a polynomial-time 8/3-approximation for the original RMVCI problem under matroids. Readers would care because these problems capture network security settings where exact computation is intractable yet good randomized strategies are needed.

Core claim

The authors show that the randomized max-vertex-cover interdiction problem under matroid constraints admits a polynomial-time 8/3-approximation algorithm. They achieve this by proving that the linear-programming relaxation of the follower's integer program has a tight integrality gap of 4/3, then substituting that relaxation into the bilevel program. Shifting the leader's mixed strategy from set distributions to vertex distributions and applying their conceptual approximation framework for general bilevel interdiction problems yields a 2-approximation for the relaxed version, which composes to the claimed 8/3 factor for the original problem.

What carries the argument

The approximation framework for bilevel interdiction problems that substitutes the follower's LP relaxation and shifts leader strategies from set distributions to vertex distributions.

If this is right

The RMVCI problem under matroid constraints has a polynomial-time 8/3-approximation algorithm.
The follower's max-vertex-cover problem under matroid constraints has an LP relaxation with tight 4/3 integrality gap.
The relaxed bilevel version admits a polynomial-time 2-approximation algorithm.
The same framework applies to other bilevel interdiction problems whose follower responses admit bounded-integrality-gap LPs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same relaxation-plus-shift technique may extend to interdiction problems on other matroid-constrained follower objectives beyond vertex cover.
Any future improvement to the 4/3 gap or the 2-approximation factor would immediately tighten the overall 8/3 ratio.
The resulting randomized strategies could be evaluated on concrete network data sets to measure how close the guarantee comes to observed performance.

Load-bearing premise

Substituting the follower's LP relaxation into the bilevel program and shifting from set to vertex distributions does not introduce approximation loss beyond the product of the 2- and 4/3-factors.

What would settle it

A concrete instance in which the algorithm's returned leader strategy produces expected follower payoff strictly larger than 8/3 times the true optimal leader payoff would disprove the guarantee.

read the original abstract

We study a new bilevel optimization problem, termed the Randomized Max-Vertex-Cover Interdiction (RMVCI) problem under matroid constraints, which can be modeled as a zero-sum Stackelberg game on a network between a leader and a follower. The leader randomly selects a subset of vertices to protect, subject to a matroid constraint, while the follower-after inferring the leader's protection probability distribution-chooses a subset of vertices (also matroid-constrained) to attack, aiming to maximize the expected total weight of edges incident to the set of vertices that are both attacked and unprotected. The leader's objective is to determine an optimal randomized interdiction strategy that minimizes the follower's expected payoff. Since the follower's response problem is NP-hard, the resulting bilevel program is computationally challenging. We develop a conceptual approximation framework for tackling general bilevel interdiction problems. For the RMVCI problem under matroid constraints, we first formulate the follower's problem as an integer linear program and show that its linear relaxation admits a tight integrality gap of $\tfrac{4}{3}$. Within the approximation framework, we replace the follower's problem by its LP relaxation, and then study the resulting bilevel program. By shifting from distributions over sets to distributions over vertices and applying our approximation framework, we manage to design a polynomial-time 2-approximation algorithm for this relaxed bilevel problem. Combining these ingredients within our framework yields a polynomial-time $\tfrac{8}{3}$-approximation algorithm for RMVCI under matroid constraints.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines a new RMVCI bilevel problem on matroids and claims an 8/3-approximation by relaxing the follower LP (4/3 gap) then shifting to vertex distributions (2-approx), but the product may hide extra loss from marginalization.

read the letter

The main takeaway is a new interdiction variant with a concrete 8/3-approximation algorithm built from an LP relaxation of the follower and a set-to-vertex distribution shift inside a bilevel framework. The formulation itself is fresh, and they show the follower's LP has a tight 4/3 integrality gap, which is useful to record. The framework for handling general bilevel interdiction by swapping in the LP and then approximating the resulting game is a reasonable way to get a polynomial algorithm where the original is hard. That part is honest progress on a specific problem class. The soft spot sits in the composition step. The 4/3 gap applies to the follower alone, and the 2-approx comes from moving to vertex marginals, but the leader's randomized strategy and the follower's best response sit on top of both. Marginalizing over matroid bases to vertices can change the game value in ways that do not multiply cleanly with the integrality gap; any additional factor there would push the guarantee above 8/3. The abstract states the product without an explicit interaction bound, so the full proof needs to show that the shift loss is controlled inside the bilevel structure rather than assumed to be independent. If that step is tight, the result holds; if not, the ratio is only a starting point. This is the kind of paper combinatorial optimization people working on interdiction or matroid-constrained games would read. It is not paradigm-shifting but gives a usable ratio and a reusable relaxation trick for similar Stackelberg settings. It deserves peer review so referees can check the gap composition and any missing error terms in the distribution shift.

Referee Report

2 major / 1 minor

Summary. The paper introduces the Randomized Max-Vertex-Cover Interdiction (RMVCI) problem under matroid constraints as a zero-sum Stackelberg game in which the leader selects a randomized vertex protection set subject to a matroid constraint and the follower, after observing the protection distribution, selects a matroid-constrained attack set to maximize the expected weight of edges incident to attacked but unprotected vertices. Because the follower's integer program is NP-hard, the authors develop a general approximation framework for bilevel interdiction problems. They formulate the follower's problem as an ILP, prove that its LP relaxation has a tight 4/3 integrality gap, replace the follower by its LP relaxation, obtain a 2-approximation for the resulting relaxed bilevel program by shifting from distributions over matroid bases to vertex marginals, and combine the ingredients to claim a polynomial-time 8/3-approximation for the original RMVCI problem.

Significance. If the central claims hold, the work supplies the first constant-factor approximation algorithm for a new class of randomized network interdiction problems with matroid constraints. The proposed conceptual framework for approximating general bilevel interdiction problems may be reusable beyond this setting. The tight 4/3 integrality gap for the follower's LP and the explicit polynomial-time algorithms constitute concrete technical contributions to approximation algorithms for combinatorial interdiction.

major comments (2)

[Abstract] Abstract: the claim that the composition of the 4/3 LP integrality gap with the 2-approximation for the vertex-marginal relaxed bilevel program yields an 8/3-approximation requires that the marginalization step introduces no additional multiplicative loss that compounds with the integrality gap. The manuscript must supply an explicit bound on any interaction term between the LP substitution and the shift from set distributions to vertex marginals under the leader's randomization and the follower's best-response structure; without it the product bound is not guaranteed.
[Framework description] Framework description (the section presenting the general bilevel approximation framework): the argument that substituting the follower's LP relaxation into the bilevel program preserves a 4/3 factor relative to the true bilevel value must be shown to be independent of the subsequent vertex-distribution relaxation; any dependence would invalidate the clean multiplication to 8/3.

minor comments (1)

[Abstract] The abstract would benefit from a one-sentence statement of the precise matroid constraints used on both leader and follower sides.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to explicitly address the composition of the approximation factors. We clarify the independence of the bounds below and will revise the manuscript to include the requested details.

read point-by-point responses

Referee: [Abstract] Abstract: the claim that the composition of the 4/3 LP integrality gap with the 2-approximation for the vertex-marginal relaxed bilevel program yields an 8/3-approximation requires that the marginalization step introduces no additional multiplicative loss that compounds with the integrality gap. The manuscript must supply an explicit bound on any interaction term between the LP substitution and the shift from set distributions to vertex marginals under the leader's randomization and the follower's best-response structure; without it the product bound is not guaranteed.

Authors: We agree that an explicit clarification strengthens the presentation. The follower's payoff (both integer and LP) is linear in the leader's per-vertex protection probabilities. Consequently, the expected payoff for any fixed follower attack depends only on the marginal protection vector, independent of correlations in the leader's distribution over sets. The 4/3 integrality gap holds for the follower's problem under any protection probability vector (the gap proof relies solely on the attack matroid and edge weights). The shift to vertex marginals is exact for matroids, as any marginal vector in the matroid polytope is realizable by a convex combination of bases. Thus the 2-approximation applies directly to the relaxed bilevel optimum, and the chain is: achieved value (true payoff) ≤ achieved LP value ≤ 2 × relaxed bilevel optimum ≤ 2 × (4/3) × true bilevel optimum, with no extra interaction factor. We will add a concise paragraph to the abstract and framework section stating this independence explicitly. revision: yes
Referee: [Framework description] Framework description (the section presenting the general bilevel approximation framework): the argument that substituting the follower's LP relaxation into the bilevel program preserves a 4/3 factor relative to the true bilevel value must be shown to be independent of the subsequent vertex-distribution relaxation; any dependence would invalidate the clean multiplication to 8/3.

Authors: The 4/3 factor is obtained by observing that, for every leader strategy s, max_LP(s) ≤ (4/3) max_IP(s). Taking the minimum over s yields relaxed_bilevel_opt ≤ (4/3) true_bilevel_opt. This inequality holds for any representation of s, including vertex marginals, because the gap depends only on the induced protection probabilities. The subsequent 2-approximation via marginals is performed exclusively on the already-relaxed (LP-follower) bilevel program and is measured relative to its own optimum. No further loss is introduced that interacts with the gap, as the linearity argument above ensures the gap bound is invariant to the marginalization step. We will revise the framework section to include a short lemma formalizing this independence and the resulting multiplicative 8/3 guarantee. revision: yes

Circularity Check

0 steps flagged

Minor self-citation of general approximation framework; central 8/3 ratio derived independently from LP gap and designed 2-approx

full rationale

The paper directly establishes the 4/3 integrality gap of the follower's LP relaxation and designs a separate 2-approximation algorithm for the relaxed bilevel problem via the set-to-vertex distribution shift. The final 8/3 guarantee is obtained by composing these two factors inside the framework. No equation or claim reduces the target approximation ratio to a fitted input, self-definition, or unverified self-citation chain; the framework supplies reusable algorithmic machinery rather than defining the result by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of matroids and the integrality gap of the vertex-cover LP relaxation; no new entities or fitted parameters are introduced.

axioms (2)

standard math Matroids satisfy the standard independence axioms (hereditary and augmentation properties)
Invoked to constrain both leader protection sets and follower attack sets.
domain assumption The linear relaxation of the follower's integer program has integrality gap exactly 4/3
Stated as shown in the paper and used to bound the approximation.

pith-pipeline@v0.9.0 · 5578 in / 1311 out tokens · 53931 ms · 2026-05-12T04:55:24.334360+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Journal of Combinatorial Optimization8(3), 307–328 (2004)

Ageev, A.A., Sviridenko, M.I.: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization8(3), 307–328 (2004)

work page 2004
[2]

Operations Research Letters44(1), 114–120 (2016)

Bertsimas, D., Nasrabadi, E., Orlin, J.B.: On the power of randomization in network interdiction. Operations Research Letters44(1), 114–120 (2016)

work page 2016
[3]

In: International Conference on Integer Programming and Combinatorial Optimization (IPCO)

Calinescu, G., Chekuri, C., P´ al, M., Vondr´ ak, J.: Maximizing a submodular set function subject to a matroid constraint. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). vol. 4513, pp. 182–196. Springer (2007)

work page 2007
[4]

Operations Research Letters46(2), 185–188 (2018)

Carvalho, M., Lodi, A., Marcotte, P.: A polynomial algorithm for a continuous bilevel knapsack problem. Operations Research Letters46(2), 185–188 (2018)

work page 2018
[5]

Theoret- ical Computer Science497, 1–12 (2013)

Chen, L., Zhang, G.: Approximation algorithms for a bi-level knapsack problem. Theoret- ical Computer Science497, 1–12 (2013)

work page 2013
[6]

Annals of the Association of American Geographers94(3), 491–502 (2004)

Church, R.L., Scaparra, M.P., Middleton, R.S.: Identifying critical infrastructure: the median and covering facility interdiction problems. Annals of the Association of American Geographers94(3), 491–502 (2004)

work page 2004
[7]

Mathematical Programming183(1), 249–281 (2020) 14

Croce, F.D., Scatamacchia, R.: An exact approach for the bilevel knapsack problem with in- terdiction constraints and extensions. Mathematical Programming183(1), 249–281 (2020) 14

work page 2020
[8]

Journal of Combinatorial Theory, Series B36(2), 161–188 (1984)

Cunningham, W.H.: Testing membership in matroid polyhedra. Journal of Combinatorial Theory, Series B36(2), 161–188 (1984)

work page 1984
[9]

In: International Conference on Integer Programming and Combinatorial Optimization (IPCO)

Dinitz, M., Gupta, A.: Packing interdiction and partial covering problems. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 157–168. Springer (2013)

work page 2013
[10]

Combinatorial Struc- tures and Their Applications pp

Edmonds, J.: Submodular functions, matroids and certain polyhedra. Combinatorial Struc- tures and Their Applications pp. 69–87 (1970)

work page 1970
[11]

In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Frederickson, G.N., Solis-Oba, R.: Increasing the weight of minimum spanning trees. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 539–546. ACM/SIAM (1996)

work page 1996
[12]

Mathematical Programming13(1), 116–118 (1977)

Fulkerson, D.R., Harding, G.C.: Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming13(1), 116–118 (1977)

work page 1977
[13]

Gr¨ otschel, M., Lov´ asz, L., Schrijver, A.: Geometric algorithms and combinatorial optimiza- tion, vol. 2. Springer (1988)

work page 1988
[14]

Operations Research69(1), 82–99 (2021)

Holzmann, T., Smith, J.C.: The shortest path interdiction problem with randomized inter- diction strategies: Complexity and algorithms. Operations Research69(1), 82–99 (2021)

work page 2021
[15]

Theoretical Computer Science 965, 113977 (2023)

Huang, C.C., Sellier, F.: Matroid-constrained vertex cover. Theoretical Computer Science 965, 113977 (2023)

work page 2023
[16]

In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC)

Phillips, C.A.: The network inhibition problem. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC). pp. 776–785 (1993)

work page 1993
[17]

European Journal of Operations Research283(3), 797–811 (2020)

Smith, J.C., Song, Y.: A survey of network interdiction models and algorithms. European Journal of Operations Research283(3), 797–811 (2020)

work page 2020
[18]

Operations Research12(6), 934–940 (1964)

Wollmer, R.: Removing arcs from a network. Operations Research12(6), 934–940 (1964)

work page 1964
[19]

Discrete Applied Mathematics158(15), 1676–1690 (2010) 15

Zenklusen, R.: Matching interdiction. Discrete Applied Mathematics158(15), 1676–1690 (2010) 15

work page 2010