Introduction

Given a graph and a required set of vertices, the goal is to find the smallest connected subgraph that contains all of those required vertices. In general graphs this is closely related to the Steiner tree problem, which is computationally hard, but several special cases and practical approximations are very useful.

The Problem Behind the Name

Suppose you have a graph and a subset of vertices called terminals. You want a connected subgraph that includes every terminal while using as little structure as possible. "As little as possible" might mean:

• fewest edges
• lowest total edge weight
• fewest added non-terminal vertices

In an unweighted graph, minimizing the number of edges is the natural interpretation. In a weighted graph, the usual objective is minimum total weight.

This is not the same as a minimum spanning tree. A minimum spanning tree connects all vertices in the graph. Here, only the terminal set must be connected, and the solution may add a few extra non-terminal vertices if they help connect the terminals cheaply.

Those extra helper vertices are called Steiner vertices.

Relation to the Steiner Tree Problem

For a general graph, the minimum connected subgraph containing a given set of nodes is the Steiner tree problem. That matters because the Steiner tree problem is NP-hard, so there is no known polynomial-time algorithm for all cases.

Still, the problem is not hopeless. There are three common ways to deal with it:

1. solve special graph families exactly
2. use dynamic programming when the terminal count is small
3. use approximation or heuristics for larger graphs

If your graph is a tree, the problem becomes much easier. The minimal connected subgraph is simply the union of the unique paths between the terminals.

Exact Solution on a Tree

Trees are the cleanest case because there is exactly one simple path between any two vertices. A practical way to compute the answer is:

1. start with the full tree
2. repeatedly prune leaves that are not terminals
3. stop when every leaf is a terminal

The remaining edges form the minimum connected subgraph containing the required nodes.

Here is a runnable Python example:

1from collections import defaultdict, deque
2
3
4def minimal_terminal_subtree(n, edges, terminals):
5    graph = defaultdict(set)
6    degree = [0] * n
7    terminals = set(terminals)
8
9    for u, v in edges:
10        graph[u].add(v)
11        graph[v].add(u)
12        degree[u] += 1
13        degree[v] += 1
14
15    queue = deque(i for i in range(n) if degree[i] <= 1 and i not in terminals)
16    removed = [False] * n
17
18    while queue:
19        node = queue.popleft()
20        if removed[node]:
21            continue
22        removed[node] = True
23
24        for neighbor in list(graph[node]):
25            graph[neighbor].remove(node)
26            degree[neighbor] -= 1
27            if degree[neighbor] == 1 and neighbor not in terminals:
28                queue.append(neighbor)
29
30        graph[node].clear()
31
32    result_edges = []
33    for u in range(n):
34        for v in graph[u]:
35            if u < v:
36                result_edges.append((u, v))
37    return result_edges
38
39
40edges = [(0, 1), (1, 2), (1, 3), (3, 4), (3, 5)]
41terminals = [2, 4, 5]
42print(minimal_terminal_subtree(6, edges, terminals))

For this tree, the result is the smallest subtree that still connects vertices 2, 4, and 5.

What Changes in General Graphs

In a general graph, there may be many candidate paths between terminals. Sometimes the best solution includes a non-terminal vertex because it lets several terminals share part of the route. That sharing is exactly why the problem is harder than just joining terminals with independent shortest paths.

A common approximation strategy is:

1. compute shortest-path distances between every pair of terminals
2. build a complete graph on the terminals using those distances
3. compute a minimum spanning tree in that terminal graph
4. expand each terminal edge back into the original shortest path

This does not always produce the optimal Steiner tree, but it is a useful and understandable baseline.

When This Appears in Practice

This problem shows up in network design, VLSI routing, road planning, multicast distribution, and biological pathway analysis. The theme is always the same: connect a required set cheaply without forcing the rest of the graph into the solution.

Because exact optimization is expensive in large graphs, engineering solutions often combine:

• preprocessing to remove obviously irrelevant vertices
• heuristics based on shortest paths
• local improvement after building an initial tree

That is usually a better practical strategy than insisting on exact optimality at all costs.

Common Pitfalls

The first mistake is confusing the problem with a minimum spanning tree. If the graph has many irrelevant vertices, an MST solves a different problem.

Another common mistake is assuming the union of pairwise shortest paths is always optimal. It can work as a heuristic, but the combined structure may contain unnecessary edges or miss a cheaper shared connection through a different Steiner vertex.

On trees, developers sometimes overcomplicate the solution. The prune-non-terminal-leaves method is simple, exact, and efficient.

Finally, always clarify the objective. Minimum by edge count and minimum by total weight can produce different answers.

Summary

• The minimum connected subgraph for a required node set is the Steiner tree problem in general graphs.
• The problem is NP-hard in general, so approximations are often necessary.
• On a tree, the exact answer is easy: prune non-terminal leaves until only the required subtree remains.
• A minimum spanning tree is not the same problem unless all vertices are required.
• Clear definition of the cost function is essential before choosing an algorithm.