6
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This problem is well-studied under the name "three-in-a-tree" and more generally "k-in-a-tree". $\endgroup$
    – Laakeri
    Jan 1 at 21:47
  • $\begingroup$ @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. $\endgroup$
    – Michael Lampis
    Jan 2 at 10:40

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.