Unary Sum of Square Partition → Bidirected-Tree Periodic Waiting-Time Minimization Complexity open
Unsolved
Why this question matters
Moderate: it would classify the directed analogue of a recent temporal-network design problem, relevant when two directions of a transit link have separate departure phases.
Meusel et al. (SAND 2026, Corollary 3.4 and Section 4) prove undirected-tree hardness and explicitly ask for the directed case; they state that direct transfer to bidirected trees seems unlikely because reverse paths are arc-disjoint. The target here is bidirected trees, a narrow natural directed case.
The reduction to construct
Input is a unary-encoded multiset A of positive integers, an integer q, and threshold T. Output YES exactly if A can be partitioned into q parts with the sum of squared part sums at most T; otherwise NO.
Input is an explicitly listed bidirected tree, a positive integer period Δ, and a binary threshold K. Assign each directed arc independently one residue in {0,…,Δ−1}, repeated every Δ time units. For every ordered vertex pair, use its unique directed path and the fastest strictly increasing traversal; sum duration minus static path length. Output YES if some arc labeling gives total excess time at most K, otherwise NO.
Give a deterministic polynomial-time F from unary Sum of Square Partition and truth-preserving G, proving NP-hardness for bidirected-tree periodic waiting minimization.
High: the undirected reduction makes both travel directions share an edge label, yielding a sum-of-squares identity. In a bidirected tree the reverse paths use separate arcs, so a local gadget must couple their phase choices without changing all-pairs costs.
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 2026-09-26: "bidirected trees waiting time minimization 2026", "Sum of Square Partition temporal tree", and board aliases. Read SAND 2026 Definitions 2.1–2.4, Corollary 3.4 and Section 4. No later matching classification found in indexed results. Gate 5 route: encode each undirected phase by paired arcs with a high-multiplicity consistency gadget; missing is a proof that independent reverse phases cannot lower the objective below the intended threshold. Untested; Gate 6 not assessed.