Source: OPTIMAL LINEAR ARRANGEMENT
Target: ROOTED TREE ARRANGEMENT

Status: Blocked — witness extraction is not possible with the current architecture (see below).

Motivation: Establishes NP-completeness of ROOTED TREE ARRANGEMENT by reduction from OPTIMAL LINEAR ARRANGEMENT. Both problems concern arranging graph vertices to minimize total stretch of edges, but the tree arrangement variant embeds vertices into a rooted tree rather than a linear order, generalizing the layout structure.

Reference: Garey & Johnson, Computers and Intractability, A1.3, GT45; Gavril 1977a

GJ Source Entry

GT45 ROOTED TREE ARRANGEMENT
INSTANCE: Graph G = (V,E), positive integer K.
QUESTION: Is there a rooted tree T = (U,F) with |U| = |V| and a one-to-one function f: V → U such that, for every edge {u,v} ∈ E, the unique path in T from the root to some vertex of U contains both f(u) and f(v), and such that Σ_{{u,v}∈E} d_T(f(u), f(v)) ≤ K, where d_T denotes distance in the tree T?
Reference: [Gavril, 1977a]. Transformation from OPTIMAL LINEAR ARRANGEMENT.

Why This Reduction Cannot Be Implemented

The core problem: OLA is a restriction of RTA

A linear arrangement is a special case of a rooted tree arrangement (a path P_n is a degenerate rooted tree). Therefore:

• OLA ⊆ RTA: every feasible OLA solution (a permutation on a path) is a feasible RTA solution.
• opt(RTA) ≤ opt(OLA): RTA can search over all rooted trees, not just paths, so it may find strictly better solutions.

Forward direction works, backward direction fails

As a decision reduction OLA → RTA with identity mapping (G' = G, K' = K):

• Forward (⟹): If OLA has a solution with cost ≤ K, then RTA has a solution with cost ≤ K (use the path tree). ✅
• Backward (⟸): If RTA has a solution with cost ≤ K using a non-path tree, there is no way to extract a valid OLA solution. The RTA-optimal tree may be branching, and no linear arrangement achieves the same cost. ❌

Witness extraction is broken

The codebase requires ReduceTo<T> with witness extraction: given a target solution, produce a valid source solution. For this reduction, the target (RTA) may return a non-path-tree embedding. There is no general procedure to convert an arbitrary rooted-tree embedding back into a linear arrangement while preserving the cost bound.

What about the Gavril 1977a reference?

The GJ entry states that RTA's NP-completeness is proved "by transformation from OLA." The actual Gavril construction likely uses a non-trivial gadget that modifies the graph to force the optimal tree to be a path, ensuring the backward direction holds. The identity mapping (G' = G, K' = K) proposed in the original version of this issue is insufficient.

Possible resolution paths

1. Decision-reduction support: If the codebase adds support for decision reductions (yes/no without witness extraction), the forward direction alone suffices to prove NP-hardness.
2. Recover the original Gavril construction: The actual 1977a paper may contain a gadget-based construction that forces path-tree solutions, enabling witness extraction. This would require locating and carefully implementing the original construction.
3. Reverse direction (RTA → OLA): Not useful — RTA generalizes OLA, so reducing RTA to OLA would require showing that trees can be linearized without cost increase, which is false in general.

References

• Gavril, F. (1977a). Some NP-complete problems on graphs. In Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91–95, Johns Hopkins University.
• Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Problem GT45.