Steiner Tree

Overview

The Steiner Tree algorithm finds a minimum-weight tree that connects a set of terminal nodes through a specified root node. Unlike a minimum spanning tree which connects all nodes, a Steiner tree only needs to connect the specified terminals — it may include additional intermediate nodes (called Steiner nodes) if they help reduce the total weight.

Applications:

• Network design: Finding the cheapest way to connect a subset of locations.
• VLSI circuit design: Connecting pins with minimum wiring.
• Multicast routing: Connecting a set of receivers to a source.

Concepts

Steiner Tree

Given a graph, a root node, and a set of terminal nodes, the Steiner tree is the minimum-weight subgraph that connects the root to all terminals. The problem is NP-hard, so this implementation uses an approximation:

1. For each terminal node, find the shortest path from the root to that terminal.
2. Union all these shortest paths into a single tree.
3. Remove redundant edges to produce a minimal tree.

This heuristic may not find the optimal Steiner tree, but runs efficiently and produces good results in practice.

Considerations

• The algorithm follows outgoing edges only.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (H:default {_id: "H"}),
       (A)-[:default {distance: 1}]->(B), (A)-[:default {distance: 2.4}]->(C),
       (A)-[:default {distance: 1.2}]->(D), (A)-[:default {distance: 0.7}]->(E),
       (A)-[:default {distance: 2.2}]->(F), (A)-[:default {distance: 1.6}]->(G),
       (A)-[:default {distance: 0.4}]->(H), (B)-[:default {distance: 1.3}]->(C),
       (C)-[:default {distance: 1}]->(D), (D)-[:default {distance: 1.65}]->(H),
       (E)-[:default {distance: 1.27}]->(F), (E)-[:default {distance: 0.9}]->(G),
       (F)-[:default {distance: 0.45}]->(G)

Parameters

Run Mode

Returns:

GQL
CALL algo.steiner({
  rootNode: "A",
  terminalNodes: ["C", "F"],
  weightProperty: "distance"
}) YIELD sourceId, targetId, weight

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.steiner.stream({
  rootNode: "A",
  terminalNodes: ["C", "F", "E"],
  weightProperty: "distance"
}) YIELD sourceId, targetId, weight
RETURN sourceId, targetId, weight

Result:

Terminal E is already on the path A→E→F, so adding it doesn't introduce new edges.

Stats Mode

Returns:

GQL
CALL algo.steiner.stats({
  rootNode: "A",
  terminalNodes: ["C", "F", "E"],
  weightProperty: "distance"
}) YIELD edgeCount, totalWeight

Result: