Partial Domination on hypercubes → Two-alternation hypercube routing Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
This asks whether allowing a second alternation changes the complexity of a tightly constrained reconfigurable network model.
The cited routing work distinguishes restrictions on dynamic edges from restrictions on alternations. A construction for one alternation does not automatically cover two.
The reduction to construct
The source gives d≥1, an explicit binary activity array of length 2ᵈ defining T, and k≥0. Its outputs are subsets X⊆T of size at most k that dominate the cube graph induced by T, or NO-SOLUTION.
The target gives a hypercube dimension ℓ≥1 in unary, positive integer weighted ordered demands between distinct vertices, and a nonnegative integer K. A valid output is a partial matching whose demand-weighted shortest-route cost is at most K/2. Static edges cost 1, matching edges cost 1/2, and each route changes link medium at most twice. Every vertex has one switch port; there are no capacity or congestion constraints. Return NO-SOLUTION if no matching qualifies.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
The proof must account for every admissible route and matching, with size measured against the explicit hypercube input.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.