[Model] OptimumCommunicationSpanningTree

[isPANN]

Motivation

OPTIMUM COMMUNICATION SPANNING TREE (ND7) from Garey & Johnson, A2. Given a complete weighted graph with communication requirements between vertex pairs, find a spanning tree that minimizes the total weighted communication cost. NP-hard even when all requirements are equal. Polynomial when all edge weights are equal (Hu 1974, solved by the Gomory-Hu tree). Fundamental in communication network design, where edge weights represent link costs and requirements represent traffic demands.

Definition

Name: OptimumCommunicationSpanningTree
Reference: Garey & Johnson, Computers and Intractability, A2 ND7; Johnson, Lenstra, and Rinnooy Kan 1978

Mathematical definition:

INSTANCE: Complete graph G = (V, E), weight w(e) ∈ Z₀⁺ for each e ∈ E, requirement r({u,v}) ∈ Z₀⁺ for each pair {u,v} of vertices from V.
OBJECTIVE: Find a spanning tree T for G that minimizes Σ_{u,v ∈ V} [W_T({u,v}) · r({u,v})], where W_T({u,v}) denotes the sum of the weights of the edges on the unique path joining u and v in T.

Variables

• Count: m = |E| = n(n-1)/2 (one binary variable per edge of the complete graph)
• Per-variable domain: {0, 1}
• Meaning: Whether each edge is included in the spanning tree. The selected n-1 edges must form a spanning tree minimizing the total weighted communication cost.

Schema

Type name: OptimumCommunicationSpanningTree
Variants: weight: i32

Field	Type	Description
num_vertices	usize	Number of vertices n
edge_weights	Vec<Vec<W>>	Symmetric weight matrix w(i,j) for each edge
requirements	Vec<Vec<W>>	Symmetric requirement matrix r(i,j) for each vertex pair

Complexity

• Best known exact algorithm: NP-hard (Johnson, Lenstra, and Rinnooy Kan 1978). Solved exactly by enumerating all labeled spanning trees (Cayley's formula: n^{n-2} trees) and evaluating communication cost for each. No known sub-exponential exact algorithm.
• Special cases:
  • All requirements equal: still NP-hard. Equivalent to minimum routing cost spanning tree (MRCT).
  • All weights equal: polynomial time, solved by the Gomory-Hu tree (Hu 1974).

Extra Remark

Full book text:

INSTANCE: Complete graph G = (V, E), a weight w(e) ∈ Z₀⁺ for each e ∈ E, a requirement r({u,v}) ∈ Z₀⁺ for each pair {u,v} of vertices from V, and a bound B ∈ Z₀⁺.
QUESTION: Is there a spanning tree T for G such that, if W({u,v}) denotes the sum of the weights of the edges on the path joining u and v in T, then Σ_{u,v ∈ V} [W({u,v}) · r({u,v})] ≤ B?

Reference: [Johnson, Lenstra, and Rinnooy Kan, 1978]. Transformation from X3C.
Comment: Remains NP-complete even if all requirements are equal. Can be solved in polynomial time if all edge weights are equal [Hu, 1974].

Note: The original G&J formulation is a decision problem with bound B. We use the equivalent optimization formulation: minimize total communication cost.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all spanning trees, compute path costs for all vertex pairs, evaluate the objective.)
• It can be solved by reducing to integer programming. (ILP with binary edge variables, multi-commodity flow for path cost computation, minimize weighted sum.) See companion issue [Rule] OptimumCommunicationSpanningTree to ILP #967.
• Other:

Reduction Rule Crossref

• [Rule] OptimumCommunicationSpanningTree to ILP #967 — [Rule] OptimumCommunicationSpanningTree to ILP (direct ILP formulation)

Example Instance

Input:
Complete graph K_4 with V = {v0, v1, v2, v3} (n = 4).

Edge weights w(i,j):

	v0	v1	v2	v3
v0	0	1	3	2
v1	1	0	2	4
v2	3	2	0	1
v3	2	4	1	0

Requirements r(i,j) (varying, not all equal):

	v0	v1	v2	v3
v0	0	2	1	3
v1	2	0	1	1
v2	1	1	0	2
v3	3	1	2	0

Optimal tree T: edges {(v0,v1), (v0,v3), (v2,v3)}, weights 1, 2, 1.
Path costs W_T:

• W(v0,v1) = 1, W(v0,v2) = 2+1 = 3, W(v0,v3) = 2
• W(v1,v2) = 1+2+1 = 4, W(v1,v3) = 1+2 = 3, W(v2,v3) = 1

Total cost = W·r = 1·2 + 3·1 + 2·3 + 4·1 + 3·1 + 1·2 = 2+3+6+4+3+2 = 20

Suboptimal tree: edges {(v0,v1), (v1,v2), (v2,v3)}, cost = 24.
Worst tree: edges {(v0,v2), (v1,v2), (v1,v3)}, cost = 58.

Expected Outcome

Optimal value: Min(20) — the minimum total communication cost is 20. Out of 16 spanning trees of K_4, there are 10 distinct cost values ranging from 20 to 58. The varying requirements (high r(v0,v3) = 3) favor trees where v0 and v3 are close, which drives the optimal tree to include the direct edge (v0,v3).

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reductions to/from existing problems — orphan node
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	✅ Pass	References verified; complexity claims substantively correct
Well-written	❌ Fail	Missing Expected Outcome section; example uses degenerate requirements

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

The problem OptimumCommunicationSpanningTree does not yet exist in the codebase. However, the issue body contains no mention of any planned reduction connecting this problem to the existing reduction graph — no "reduces to/from X", no linked [Rule] issues, and no "Reduction Rule Crossref" section. A problem without any planned reduction rule is an orphan node with no value in the reduction graph.

Action required: Add at least one concrete planned reduction to/from an existing problem (e.g., a reduction from Exact Three Cover (X3C), as mentioned in Garey & Johnson's NP-completeness proof via transformation from X3C, or a direct reduction to ILP).

Non-trivial

This is a genuinely distinct problem. The objective function — minimizing total communication cost as the sum of requirement-weighted path distances over all vertex pairs in a spanning tree — is structurally different from all existing problems in the codebase. It is not a variant of any existing spanning tree or network design problem already implemented.

Correctness

References verified:

• Johnson, Lenstra, and Rinnooy Kan (1978) — "The complexity of the network design problem," Networks 8:279–285. Confirmed real. The paper establishes NP-completeness of the network design problem, from which the OCST NP-completeness follows. The claim that the problem remains NP-complete even when all requirements are equal (reducing to the Minimum Routing Cost Spanning Tree / MRCT problem) is also confirmed in the literature.

• Hu (1974) — "Optimum Communication Spanning Trees," SIAM J. Computing 3:188–195. Confirmed real. The issue's claim that the equal-weight case is polynomial-time solvable matches Garey & Johnson's comment and Hu's original result.

• Garey & Johnson, A2 ND7 — Confirmed as a standard reference for this problem.

Complexity string "num_vertices^num_vertices" — This represents brute-force Cayley enumeration (n^{n-2} labeled spanning trees, with polynomial overhead per tree). While not the "best known exact algorithm" in the sense of an optimized exact solver, no known sub-exponential exact algorithm exists for the general case, so this is an acceptable representation of the state of the art.

Well-written

Failures:

1. Missing Expected Outcome section. The Example Instance section shows two spanning trees achieving cost 14 and states "Answer: YES" for B=14, but there is no dedicated "Expected Outcome" section identifying the optimal solution with its objective value, as required by the template. For an optimization problem phrased as a decision problem, the expected outcome should clearly state the optimal cost (14) and identify an optimal spanning tree.

2. Example uses degenerate requirements. All requirements are set to r(i,j) = 1, which reduces the problem to the Minimum Routing Cost Spanning Tree (MRCT) special case. The example fails to exercise the core distinguishing feature of OCST — the interaction between heterogeneous communication requirements and edge weights. An example with non-uniform requirements (e.g., some pairs with r=2 or r=3) would be much more illustrative and better test the implementation.

Minor observations:

• The Variable section correctly identifies n(n-1)/2 binary edge variables.
• The Schema uses symmetric matrices, which is a reasonable representation (though it stores redundant data; an upper-triangular representation would be more space-efficient).
• The naming OptimumCommunicationSpanningTree follows Garey & Johnson's convention rather than the project's Minimum/Maximum prefix convention. Since this is the established name in the literature and the problem is phrased as a decision problem with bound B (not purely an optimization problem), this is acceptable.

Recommendations

• Add non-uniform requirements to the example (e.g., r(0,1) = 3, r(2,3) = 2, others = 1) to exercise the full problem structure.
• Consider adding a direct [Rule] OptimumCommunicationSpanningTree to ILP companion issue, since the problem has a natural ILP formulation (binary edge selection with flow-based path-distance constraints).
• The transformation from X3C mentioned in Garey & Johnson could serve as a useful reduction link to the existing graph.

[isPANN]

Converted from decision to optimization framing: removed bound B, objective is now to minimize total weighted communication cost directly. Removed bound field from schema. Value type is Min<i32>.

[isPANN]

Fix-issue changelog

• Example: replaced degenerate all-equal-requirements instance with varied requirements (r values 1-3). New instance: K4 with 16 trees, 10 distinct costs, optimal Min(20). Verified by brute force.
• Expected Outcome: added section with Min(20) and cost distribution analysis
• ILP companion: created [Rule] OptimumCommunicationSpanningTree to ILP #967 [Rule] OptimumCommunicationSpanningTree to ILP, linked in How to Solve and Crossref
• Removed <!-- Unverified --> markers from verified sections

Applied by /fix-issue.