<p>This problem is well-studied under the name &quot;three-in-a-tree&quot; and more generally &quot;k-in-a-tree&quot;. A polynomial-time algorithm for three-in-a-tree is given in [1], but the complexity of <span class="math-container">$k$</span>-in-a-tree seems to be open for every fixed constant <span class="math-container">$k \ge 4$</span>.</p>
<p>[1] Chudnovsky, Maria, and Paul Seymour. &quot;The three-in-a-tree problem.&quot; Combinatorica 30.4 (2010): 387-417.</p>

CC BY-SA 4.0
2023-01-02T20:20:19.013Z
2023-01-02T20:28:00.913Z
2023-01-02T20:28:00.913Z
Laakeri
<p>Consider the following problem: we are given an undirected graph <span class="math-container">$G=(V,E)$</span> and three terminal vertices <span class="math-container">$t_1,t_2,t_3\in V$</span>. We are asked whether there exists a set of vertices <span class="math-container">$S\subseteq V$</span> such that the induced subgraph <span class="math-container">$G[S]$</span> is a tree that contains all the terminals. In other words, we want to select vertices of <span class="math-container">$G$</span> so that the terminals become connected, but <strong>without inducing any cycles</strong>.</p>
<p>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 <span class="math-container">$K_3$</span> and attach a leaf terminal to each vertex).</p>
<p>More broadly, I would be interested in the (parameterized) complexity of this problem for a fixed number <span class="math-container">$k$</span> of terminals, if any such results are known. The problem is trivial for <span class="math-container">$k=2$</span> (find a shortest path) and <span class="math-container">$k=3$</span> is the first case for which no algorithm seems obvious (to me). I think showing that the problem is NP-complete when <span class="math-container">$k$</span> is part of the input should not be too hard (but I would appreciate a reference if this is known!).</p>

CC BY-SA 4.0
2023-01-01T21:47:04.710Z
This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree".
Laakeri
CC BY-SA 4.0
2023-01-02T10:40:11.147Z
@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.
Michael Lampis
<graph-theory><np-hardness><parameterized-complexity>
Complexity of induced Steiner Tree problem
Michael Lampis
# Complexity of induced Steiner Tree problem

(Asked by: username_0 on 2023-01-01)

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!).

**Tags:** graph-theory, np-hardness, parameterized-complexity

> **Comments:**
> **username_1**: This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree".  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_1 on 2023-01-02. Score: 6 | Accepted answer

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$.

[1] Chudnovsky, Maria, and Paul Seymour. "The three-in-a-tree problem." Combinatorica 30.4 (2010): 387-417.


---

