Three-terminal Multiway Cut → Deadline-bounded Strict Temporal Edge Cut Complexity open
Unsolved
Why this question matters
Moderate: this would close the precise strict-versus-nonstrict gap in temporal network interdiction with deadlines, distinguishing it from already polynomial unrestricted strict temporal cut and already hard non-strict deadline cut.
Dondi and Lafond (WADS 2025, Theorem 13 and Section 6) prove APX-hardness only for non-strict deadline cut and explicitly ask whether strict deadline cut is NP-hard. SAND 2026 Robust Temporal Cut permits adversarial timestamp changes; its strict hardness is a different target.
The reduction to construct
Input is an explicitly listed undirected graph, three distinct terminals, and a binary edge-deletion budget k. Output YES exactly if deleting at most k edges disconnects every terminal pair; otherwise NO.
Input is an explicitly listed undirected temporal graph with timestamped edge appearances, s,z, a deadline ℓ and edge-deletion budget K, all integers binary. Output YES exactly if deleting at most K temporal edge appearances eliminates every simple s–z path with strictly increasing timestamps and duration last-minus-first-plus-one at most ℓ; otherwise NO. ℓ is part of the input and may exceed two.
Construct deterministic polynomial-time F and truth-preserving G from Multiway Cut to this strict temporal cut decision problem, proving NP-hardness of the deadline-bounded strict variant.
High: the known Multiway Cut gadget copies graph edges at one time, so long terminal-to-terminal paths cease to be legal when timestamps must increase. Layering them naively can multiply the deletion cost.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web searches 2026-09-26: "strict temporal cut deadline NP-hard 2026", "Robust Temporal Cut strict", and exact board phrases. Read WADS 2025 Problem 2, Theorem 13 proof sketch and final open questions; compared SAND 2026 robust model. No matching later theorem found within indexed results. Gate 5 route: timestamp-layer each static edge while identifying all copies with a shared budget choice; the unproved step is a cost-preserving deletion gadget. Untested; Gate 6 not assessed.