[Model] MinimumSteinerTree

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] MinimumSteinerTree"
labels: model
assignees: ''

Motivation

STEINER TREE IN GRAPHS from Garey & Johnson, A2 ND12. A classical NP-complete problem (Karp, 1972, via Set Covering; Garey & Johnson list a transformation from EXACT COVER BY 3-SETS) central to network design, VLSI layout, and phylogenetic tree reconstruction. Given a graph with weighted edges and a subset of required terminal vertices, the problem asks for the minimum-weight tree connecting all terminals. It generalizes the minimum spanning tree problem (where all vertices are terminals) and is a key source for the reduction to NETWORK RELIABILITY (ND20).

Associated rules:

• R41: STEINER TREE IN GRAPHS -> NETWORK RELIABILITY (ND20)

Definition

Name: MinimumSteinerTree
Canonical name: Steiner Tree in Graphs (also: Steiner Minimum Tree, Steiner Network Problem)
Reference: Garey & Johnson, Computers and Intractability, A2 ND12

Mathematical definition:

INSTANCE: Graph G = (V,E), a weight w(e) ∈ Z⁺₀ for each e ∈ E, and a subset R ⊆ V of required terminal vertices.
OPTIMIZATION: Find a subtree T of G that includes all the vertices of R and minimizes the total edge weight Σ_{e ∈ T} w(e).

Variables

• Count: |E| binary variables (one per edge)
• Per-variable domain: binary {0, 1} — whether edge e is included in the Steiner tree
• dims(): vec![2; num_edges] — each edge is either included (1) or excluded (0)
• Meaning: variable x_e = 1 if edge e is selected for the tree. A valid assignment forms a connected subtree spanning all terminals R. The objective is to minimize Σ w(e) · x_e over all such valid assignments. Invalid configurations (disconnected or not spanning all terminals) evaluate to SolutionSize::Invalid.

Schema (data type)

Type name: MinimumSteinerTree
Variants: graph topology (graph type parameter G), weight type (W)

Field	Type	Description
graph	SimpleGraph	The undirected weighted graph G = (V, E)
terminals	Vec<usize>	The required terminal vertices R ⊆ V
weights	Vec<W>	Edge weights w(e) for each e ∈ E

Size fields: num_vertices, num_edges, num_terminals

Notes:

• This is a minimization problem: Metric = SolutionSize<W>, implementing OptimizationProblem with Direction::Minimize.
• The optimization version minimizes the total edge weight of the Steiner tree.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|), num_terminals() (= |R|).

Complexity

• Decision complexity: NP-complete (Karp, 1972, via Set Covering; Garey & Johnson list a transformation from EXACT COVER BY 3-SETS).
• Best known exact algorithm: The Dreyfus-Wagner dynamic programming algorithm runs in O(3^k · n + 2^k · n² + n³) time and O(2^k · n) space, where k = |R| is the number of terminals and n = |V|. This was improved by Fuchs, Kern, and Wang (2007) to O*(2.684^k). Bjorklund, Husfeldt, Kaski, and Koivisto (2007, "Fourier meets Möbius: fast subset convolution," STOC 2007) achieved O*(2^k) time using subset convolution over the Möbius algebra, and Nederlof (2009) gave an O*(2^k)-time polynomial-space algorithm using Möbius inversion.
• Special cases: Polynomial-time solvable when |R| = |V| (minimum spanning tree) or |R| ≤ 2 (shortest path).

declare_variants! guidance:

declare_variants! {
    MinimumSteinerTree<SimpleGraph, i32> => "2^num_terminals * num_vertices^3",
    MinimumSteinerTree<SimpleGraph, f64> => "2^num_terminals * num_vertices^3",
}

This uses the Bjorklund et al. (2007) bound O*(2^k), the best known exact algorithm, with polynomial factor n³ from the subset convolution computation.

• References:
  • R.M. Karp (1972). "Reducibility Among Combinatorial Problems." Complexity of Computer Computations, pp. 85-103. Plenum Press.
  • S.E. Dreyfus, R.A. Wagner (1971). "The Steiner Problem in Graphs." Networks, 1(3):195-207.
  • B. Fuchs, W. Kern, X. Wang (2007). "Speeding up the Dreyfus-Wagner Algorithm for Minimum Steiner Trees." Mathematical Methods of Operations Research, 66(1):117-125.
  • A. Bjorklund, T. Husfeldt, P. Kaski, M. Koivisto (2007). "Fourier meets Möbius: fast subset convolution." Proceedings of STOC 2007, pp. 67-74. ACM.
  • J. Nederlof (2009). "Fast Polynomial-Space Algorithms Using Möbius Inversion." ICALP 2009, LNCS 5555, pp. 713-725.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), a weight w(e) in Z0+ for each e in E, a subset R <= V, and a positive integer bound B.
QUESTION: Is there a subtree of G that includes all the vertices of R and such that the sum of the weights of the edges in the subtree is no more than B?

Reference: [Karp, 1972]. Transformation from EXACT COVER BY 3-SETS.
Comment: Remains NP-complete if all edge weights are equal, even if G is a bipartite graph having no edges joining two vertices in R or two vertices in V-R [Berlekamp, 1976] or G is planar [Garey and Johnson, 1977a].

How to solve

• It can be solved by (existing) bruteforce. Enumerate all subsets of edges containing a spanning tree of the terminals R, check connectivity and compute weight.
• It can be solved by reducing to integer programming. Binary variable per edge, minimize total weight subject to connectivity constraints (subtour elimination or flow-based formulation).
• Other: Dreyfus-Wagner DP in O(3^k * n + 2^k * n^2) time; Nederlof O*(2^k) polynomial-space algorithm.

Example Instance

Graph G with 8 vertices {0, 1, 2, 3, 4, 5, 6, 7} and 12 edges:

• Terminals R = {0, 3, 5, 7} (k = 4)
• Edges with weights:
  • {0,1}: w=2, {0,2}: w=3, {1,2}: w=1, {1,3}: w=4
  • {2,4}: w=2, {3,4}: w=3, {3,5}: w=5, {4,5}: w=1
  • {4,6}: w=2, {5,6}: w=3, {5,7}: w=4, {6,7}: w=1

Optimal Steiner tree:

• Edges: {0,1}(2) + {1,2}(1) + {2,4}(2) + {4,5}(1) + {4,6}(2) + {6,7}(1) + {3,4}(3)
• Total weight: 2 + 1 + 2 + 1 + 2 + 1 + 3 = 12
• Steiner vertices used: {1, 2, 4, 6} (non-terminal vertices included to reduce total weight)
• All terminals {0, 3, 5, 7} are connected in the subtree

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; classical NP-complete problem from Karp's 21
Non-trivial	✅ Pass	Distinct feasibility constraints (connected subtree spanning terminal subset) from all existing problems
Correctness	⚠️ Warn	Minor attribution issue with NP-completeness proof; one complexity claim unverified
Well-written	⚠️ Warn	Decision/optimization formulation inconsistency; naming convention question

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. SteinerTreeInGraphs does not exist in the codebase (confirmed via pred show). It is a classical NP-complete problem (Karp's 21, GJ ND5) central to network design. It appears in the Karp reduction tree (Set Covering → Steiner Tree) and has a proposed outgoing reduction to Network Reliability. The motivation is well-articulated: network design, VLSI layout, phylogenetic reconstruction.

Non-trivial

Pass. The Steiner Tree problem has genuinely distinct feasibility constraints from all 24 existing problems. It requires finding a connected subtree spanning a designated terminal subset — no existing problem captures this "connect a subset via minimum-weight tree" structure. It is not a variant of TravelingSalesman (which requires a Hamiltonian cycle), MinimumSetCovering (which covers a universe with sets), or any graph problem currently in the codebase.

Correctness

Warn — minor issues, no fatal errors.

References verified:

1. Dreyfus & Wagner (1971) — Confirmed. "The Steiner Problem in Graphs," Networks 1(3):195-207. The O(3^k · n + 2^k · n^2 + n^3) time bound is correct for the original DP algorithm.

2. Fuchs, Kern & Wang (2007) — Confirmed. "Speeding up the Dreyfus-Wagner Algorithm for Minimum Steiner Trees," Mathematical Methods of Operations Research 66(1):117-125. The O*(2.684^k) improvement is correct.

3. Bjorklund, Husfeldt, Kaski & Koivisto (2007) — Confirmed. "Fourier meets Mobius: fast subset convolution," STOC 2007. Achieves O*(2^k) for Steiner Tree. Note: the issue says "Bjorklund, Husfeldt, Kaski, and Koivisto (2007)" which is correct, though the paper title is about subset convolution, not Steiner Tree per se — the Steiner Tree result is an application.

4. Nederlof (2009) — Confirmed. "Fast Polynomial-Space Algorithms Using Mobius Inversion," ICALP 2009, LNCS 5555, pp. 713-725. Achieves O*(2^k) in polynomial space.

5. O(1.36^n) in terms of all vertices* — This claim appears to come from Fomin, Grandoni, Kratsch, and Lokshtanov's work on Steiner Tree in polynomial space. The bound is plausible based on search results but the specific citation is missing from the issue. The issue does not cite the source for this claim.

6. NP-completeness attribution — The issue states "NP-complete (Karp, 1972; transformation from EXACT COVER BY 3-SETS)." This is taken verbatim from the Garey & Johnson book. However, Karp's 1972 paper actually reduces Steiner Tree from Set Covering in his reduction tree. The "transformation from Exact Cover by 3-Sets" appears to be the specific reduction used in Garey & Johnson (1979), not Karp (1972). This is a minor attribution imprecision inherited from the GJ book text — not a fatal error, but worth noting.

Well-written

Warn — mostly complete, a few items to address:

4a: Information Completeness — All required sections are present and substantive. Good.

4b: Definition Completeness — The formal definition is the decision version (with bound B and a yes/no question), but the Schema section says Metric = SolutionSize<W> implementing OptimizationProblem with Direction::Minimize. This is a formulation mismatch:

• The bound field in the schema belongs to the decision version
• If implementing as OptimizationProblem (which is the codebase convention for minimization problems), the bound B should not be a field — the objective is simply to minimize total edge weight
• Recommendation: Remove the bound field from the schema and rewrite the Definition section as an optimization problem: "Find a subtree of G that includes all vertices of R and minimizes the sum of edge weights."

4c: Symbol and Notation Consistency

• The notation is mostly consistent. Symbols G, V, E, R, w(e), B are defined in the definition and used consistently in the Variables and Schema sections.
• The overhead metric names (num_vertices, num_edges, num_terminals) follow the codebase convention. Good.

4d: Naming Convention

• The issue proposes SteinerTreeInGraphs. The codebase convention for minimization problems uses the Minimum prefix (e.g., MinimumVertexCover, MinimumDominatingSet, MinimumSetCovering). The NP Optimization Compendium also calls it "Minimum Steiner Tree."
• However, TravelingSalesman (also a minimization problem) does not use the prefix, so there is precedent for dropping it.
• Recommendation: Consider renaming to MinimumSteinerTree for consistency with the majority of minimization problems in the codebase. The "in Graphs" suffix is also unusual — no other problem in the codebase uses such a qualifier.

4e: Example Quality — The example is well-constructed: 8 vertices, 4 terminals, 12 edges, with a fully worked Steiner tree solution of weight 12 using 4 Steiner vertices. The claim that B=11 gives NO (i.e., 12 is optimal) is stated but not proven — for a hand-verifiable example this is acceptable given the size, though a brief justification would strengthen it.

Recommendations

• Remove the bound field and reformulate as a pure optimization problem (matching OptimizationProblem trait)
• Consider renaming to MinimumSteinerTree for naming consistency
• Add the missing citation for the O*(1.36^n) bound (likely Fomin, Grandoni, Kratsch & Lokshtanov)
• The Bjorklund et al. citation could note the actual paper title ("Fourier meets Mobius: fast subset convolution") for accuracy