# Complexity of induced Steiner Tree problem

Consider the following problem: we are given an undirected graph $$G=(V,E)$$ and three terminal vertices $$t_1,t_2,t_3\in V$$. We are asked whether there exists a set of vertices $$S\subseteq V$$ such that the induced subgraph $$G[S]$$ is a tree that contains all the terminals. In other words, we want to select vertices of $$G$$ so that the terminals become connected, but without inducing any cycles.

I would probably call this problem INDUCED CONNECTING TREE, or INDUCED STEINER TREE, but I haven't been able to find any references to it. Is this problem known by another name? Note that I'm not asking to minimize the size of the tree, I only ask whether such a tree exists. The answer may be no, even in a connected graph (for example, if we take a $$K_3$$ and attach a leaf terminal to each vertex).

More broadly, I would be interested in the (parameterized) complexity of this problem for a fixed number $$k$$ of terminals, if any such results are known. The problem is trivial for $$k=2$$ (find a shortest path) and $$k=3$$ is the first case for which no algorithm seems obvious (to me). I think showing that the problem is NP-complete when $$k$$ is part of the input should not be too hard (but I would appreciate a reference if this is known!).

• This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree". Jan 1, 2023 at 21:47
• @Laakeri Thanks, this is the name I was looking for. Apparently, the complexity is open for fixed $k\ge 4$, but the problem is in P for $k=3$. If you turn your comment into an answer, I will be happy to accept it. Jan 2, 2023 at 10:40

This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree". A polynomial-time algorithm for three-in-a-tree is given in [1], but the complexity of $$k$$-in-a-tree seems to be open for every fixed constant $$k \ge 4$$.