Three-terminal Multiway Cut → Undirected Network Diversion Complexity open
Unsolved
Why this question matters
High: it would settle the hardness side of the P-versus-NP-hard classification explicitly left open for general undirected Network Diversion, with direct interpretation for forced bottlenecks in transportation and communication networks.
Bentert et al. (SEA 2025, Introduction and Section 6) give a polynomial algorithm on planar undirected graphs, note NP-hardness for directed graphs, and explicitly leave general undirected complexity open. This card pursues the hardness direction; their conjecture favors tractability, so the route is uncertain.
The reduction to construct
Input is an explicitly listed undirected graph, three distinct terminals, and an integer budget k. The output is YES exactly when at most k edges disconnect every pair of terminals; otherwise NO. All integers use binary encoding.
Input is an explicitly listed undirected graph H, distinct s,t, a designated edge b, and a binary budget K. Output YES exactly when deleting at most K edges other than b leaves at least one s–t path and makes every remaining s–t path use b; otherwise NO. The surviving-path requirement excludes a vacuous cut.
Find deterministic polynomial-time F from three-terminal Multiway Cut to Undirected Network Diversion and G that maps either target truth value to the identical correct source truth value. A positive rule proves NP-hardness of this exact undirected target.
High: the cut must separate three source terminal regions while retaining an s–t path through b. Ordinary min-cut gadgets can disconnect s from t and falsely satisfy the intended separation.
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 search on 2026-09-26: "Network Diversion general undirected complexity 2026", "Planar Network Diversion conclusion", and matching board endpoints. Read SEA 2025 Introduction, Proposition 1, and Section 6. Its planar dual-cycle argument does not apply to general graphs; no later resolution was found in this bounded search. Unindexed work remains outside coverage. Gate 5 route: use an anchored b-path to represent the surviving channel and force each forbidden terminal connection to induce a b-avoiding s–t path; the hard missing lemma is a converse for all possible deletion sets. Untested; Gate 6 not assessed.