The steiner problem in the hypercube

Let Q ( n ) be the n ‐dimensional hypercube, and X , a set of points in Q ( n ). The Steiner problem for the hypercube is to find the smallest possible number L ( n,X ) of edges in any subtree of Q ( n ) that spans X . We obtain the following results: 1 An exact formula for L ( n,X ), when | X | ≤ 5. 2 The bound L ( n,X ) ≤ ( n k +1 ) + (2 + o (1)) ([log ( k )]/ k )( n k ) as k → ∞, when X is the set of all points in Q ( n ) of a given weight k + 1, provided ( k 2 /[log ( k )]) 1 + 1/ k ≤ n . 3 NP‐completeness of deciding L ( n,X ) even when every point of X has weight at most 2.