Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse

Adam Kasperski; Marcel Jackiewicz; Pawe{\l} Zieli\'nski

arxiv: 2403.20000 · v2 · submitted 2024-03-29 · 💻 cs.CC

Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse

Marcel Jackiewicz , Adam Kasperski , Pawe{\l} Zieli\'nski This is my paper

Pith reviewed 2026-05-24 02:47 UTC · model grok-4.3

classification 💻 cs.CC

keywords recoverable robust shortest pathcomputational complexitySigma_3^p-hardnessPi_2^p-hardnessarc exclusion neighborhoodarc symmetric differencediscrete budgeted interval uncertaintyinner adversarial problem

0 comments

The pith

The recoverable robust shortest path problem is Sigma_3^p-hard for arc exclusion and arc symmetric difference neighborhoods under discrete budgeted interval uncertainty.

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

The paper strengthens existing complexity results for the recoverable robust shortest path problem by modeling second-stage arc costs with discrete budgeted interval uncertainty. It proves Sigma_3^p-hardness for the arc exclusion neighborhood and the arc symmetric difference neighborhood, along with Pi_2^p-hardness for the inner adversarial problems. A reader would care because these results place the problem at the third level of the polynomial hierarchy, indicating that exact solutions are intractable unless the hierarchy collapses and pushing reliance on heuristics for network routing under uncertainty.

Core claim

Using polynomial-time reductions, the paper shows that the recoverable robust shortest path problem is Sigma_3^p-hard for the arc exclusion neighborhood and for the arc symmetric difference neighborhood when second-stage costs follow discrete budgeted interval uncertainty. It further proves that the inner adversarial problem for each of these neighborhoods is Pi_2^p-hard.

What carries the argument

Polynomial-time reductions from known hard problems in the polynomial hierarchy to recoverable robust shortest path instances defined by the arc exclusion and arc symmetric difference neighborhoods.

If this is right

Exact solutions cannot be computed in polynomial time unless the polynomial hierarchy collapses.
The inner adversarial problem over scenarios cannot be solved in polynomial time unless the polynomial hierarchy collapses.
Practical instances of the problem on large networks require approximation or heuristic methods rather than exact solvers.

Where Pith is reading between the lines

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

Similar hardness results may hold for other graph problems that combine robustness with limited discrete recourse.
Parameterized algorithms that fix the budget size or the number of recourse arcs could still be tractable even if the general problem is hard.
The choice of neighborhood definition appears to control the precise level of hardness in the polynomial hierarchy.

Load-bearing premise

The discrete budgeted interval uncertainty representation together with the arc exclusion and arc symmetric difference neighborhood definitions permit valid polynomial-time reductions from known hard problems.

What would settle it

A polynomial-time algorithm that computes an optimal recoverable robust shortest path for the arc exclusion neighborhood on arbitrary instances would falsify the Sigma_3^p-hardness result.

read the original abstract

In this paper the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi_2^p-hard.

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

Strengthens known results to show Sigma_3^p-hardness for recoverable robust shortest path under two specific neighborhoods.

read the letter

The punchline on this paper is that it establishes Sigma_3^p-hardness for the recoverable robust shortest path with arc exclusion and arc symmetric difference neighborhoods, plus Pi_2^p-hardness for the inner problem. This strengthens previous complexity classifications in recoverable robust optimization. The authors focus on discrete budgeted interval uncertainty and show how these neighborhoods lead to higher complexity. This is useful incremental work because it identifies cases where the problem sits at specific levels of the polynomial hierarchy, which can inform when exact solutions are unlikely. The paper does well in being precise about the neighborhoods and the uncertainty model. It builds on existing literature without overclaiming. The soft spot is in the reliance on the reductions. The key is whether the constructions correctly map the quantified problems into the robust shortest path setting without the neighborhood allowing simplifications that drop the complexity. The concern about encoding the universal quantifier into the adversarial costs and recourse is something to verify in the proofs. If the budget constraint or the symmetric difference definition introduces any flexibility, it might not hold at that level. This paper is for specialists in the complexity of robust combinatorial problems. A reader looking for hardness results to guide algorithm design in network optimization would get value from the specific classifications. It deserves a serious referee to examine the reduction constructions in detail. I recommend sending it to peer review.

Referee Report

1 major / 0 minor

Summary. The manuscript studies the recoverable robust shortest path problem with discrete budgeted interval uncertainty on second-stage arc costs. It strengthens prior complexity results by proving that the overall problem is Σ₃ᵖ-hard under the arc-exclusion and arc-symmetric-difference neighborhoods and that the inner adversarial subproblem is Π₂ᵖ-hard for the same neighborhoods.

Significance. If the stated hardness results are correct, the work supplies precise placements of recoverable robust shortest-path variants inside the polynomial hierarchy. Such classifications are useful for delimiting the power of exact methods and for motivating parameterized or approximation algorithms in robust network optimization.

major comments (1)

[Theorems on Σ₃ᵖ- and Π₂ᵖ-hardness (likely §4 or §5)] The central Σ₃ᵖ- and Π₂ᵖ-hardness claims rest on polynomial-time many-one reductions whose constructions must encode the respective quantifier alternations (∃∀∃ for the outer problem, ∀∃ for the inner problem) into feasible recourse actions and cost realizations. Any slack introduced by the budgeted uncertainty set or by the precise definition of the arc-exclusion / symmetric-difference neighborhoods could collapse the alternation and place the problem in a lower class; the manuscript must therefore exhibit the explicit reduction mappings and verify that optimality is preserved.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our results and for the detailed comment on the hardness proofs. We address the concern point by point below.

read point-by-point responses

Referee: [Theorems on Σ₃ᵖ- and Π₂ᵖ-hardness (likely §4 or §5)] The central Σ₃ᵖ- and Π₂ᵖ-hardness claims rest on polynomial-time many-one reductions whose constructions must encode the respective quantifier alternations (∃∀∃ for the outer problem, ∀∃ for the inner problem) into feasible recourse actions and cost realizations. Any slack introduced by the budgeted uncertainty set or by the precise definition of the arc-exclusion / symmetric-difference neighborhoods could collapse the alternation and place the problem in a lower class; the manuscript must therefore exhibit the explicit reduction mappings and verify that optimality is preserved.

Authors: We agree that explicit verification of the reductions is essential. Sections 4 and 5 of the manuscript contain the full polynomial-time many-one reductions: from a Σ₃ᵖ-complete problem (e.g., ∃∀∃-SAT) for the outer recoverable robust problem and from a Π₂ᵖ-complete problem (e.g., ∀∃-SAT) for the inner adversarial subproblem. The constructions map the outer existential quantifier to the choice of first-stage path, the universal quantifier to adversarial cost realizations within the budgeted interval uncertainty set, and the inner existential quantifier to the recourse action under the arc-exclusion or symmetric-difference neighborhood. The budget is fixed to a value that permits exactly the adversarial choices needed to simulate the quantifier alternation; the neighborhood definitions are used verbatim so that a recourse action corresponds precisely to flipping or excluding the arcs selected by the inner existential player. We prove both directions of the reduction: (i) a yes-instance of the source problem yields a recoverable robust instance whose optimal value satisfies the threshold, and (ii) any optimal solution of the robust instance can be decoded back to a satisfying assignment without introducing slack that would allow a lower-class algorithm to solve the problem. The proofs appear in full detail; if the referee finds any step insufficiently expanded, we are prepared to add further lemmas clarifying the cost-equivalence arguments. revision: no

Circularity Check

0 steps flagged

No circularity; hardness results via explicit reductions

full rationale

The paper proves Sigma_3^p-hardness and Pi_2^p-hardness for the recoverable robust shortest path problem under discrete budgeted interval uncertainty by constructing polynomial-time many-one reductions from known complete problems in the polynomial hierarchy. These reductions are direct, self-contained constructions that encode the quantified alternations into recourse actions and cost realizations; they do not reduce to fitted parameters, self-definitions, or load-bearing self-citations. No equations or ansatzes are involved, and the central claims rest on independent proof steps rather than renaming or importing uniqueness from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard definitions from complexity theory and the problem formulation; no free parameters or invented entities are introduced in the abstract.

axioms (2)

standard math Standard definitions of the polynomial hierarchy classes Sigma_3^p and Pi_2^p and of polynomial-time reductions
Invoked to state the hardness results for the robust shortest path problem.
domain assumption The discrete budgeted interval uncertainty model and the arc exclusion / symmetric difference neighborhoods are well-defined combinatorial objects
Required for the problem statement and the claimed reductions.

pith-pipeline@v0.9.0 · 5594 in / 1305 out tokens · 22495 ms · 2026-05-24T02:47:59.616076+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

It is shown that it is Σ₃ᵖ-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Π₂ᵖ-hard.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Decision-Adv SP(Γd) with Φ(X,k) := Φ_excl(X,k) is Π₂ᵖ-complete even if k=2.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.