<p>Note that you can reduce shortest <span class="math-container">$(a,b)$</span>-Steiner path to shortest Steiner cycle by adding a terminal vertex of degree 2 adjacent to <span class="math-container">$a$</span> and <span class="math-container">$b$</span>.</p>
<p>If you are asking for derandomization of the Björklund, Husfeldt and Taslaman result, then it can be observed that the problem can be solved in FPT time using <span class="math-container">$k$</span>-disjoint paths algorithm of Robertson and Seymour as a black box (by fixing an ordering of the terminals one gets a disjoint paths problem). There is also a faster FPT algorithm (still doubly exponential dependency on <span class="math-container">$k$</span>) given by Kawarabayashi in IPCO 2008.</p>

CC BY-SA 4.0
2022-05-25T04:54:06.010Z
2022-05-25T12:00:41.997Z
2022-05-25T12:00:41.997Z
Laakeri
<p>Shortest Steiner cycle and <span class="math-container">$(a,b)$</span>-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.</p>
<p>The Shortest Steiner cycle problem is defined as follows:</p>
<blockquote>
<p>Input: An undirected and unweighted graph <span class="math-container">$G=(V,E)$</span> and <span class="math-container">$T\subseteq V$</span> (called terminals).</p>
<p>Find: Shortest cycle (minimum edges) containing all terminals.</p>
</blockquote>
<p>The Shortest <span class="math-container">$(a,b)-$</span>Steiner path problem is defined as follows:</p>
<blockquote>
<p>Input: An undirected and unweighted graph <span class="math-container">$G=(V,E)$</span>, <span class="math-container">$T\subseteq V$</span> (called terminals) and two specific terminals <span class="math-container">$a,b \in T$</span>.</p>
<p>Find: Shortest simple path (minimum edges) containing all terminals, which starts at <span class="math-container">$a$</span> and ends at <span class="math-container">$b$</span>.</p>
</blockquote>
<p>Are there XP (or even possibly FPT) algorithms known for these related problems, by parameter <span class="math-container">$k=|T|$</span>?</p>
<p>PS: I could find only a randomized FPT algorithm for the Shortest Steiner cycle problem with runtime <span class="math-container">$2^{k}n^{\mathcal{O}(1)}$</span> in <a href="https://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=&amp;cad=rja&amp;uact=8&amp;ved=2ahUKEwjyuKXy1ff3AhUTuKQKHTiXDewQFnoECCMQAQ&amp;url=https%3A%2F%2Fepubs.siam.org%2Fdoi%2Fpdf%2F10.1137%2F1.9781611973099.139&amp;usg=AOvVaw15HxMpVOkgYwKQYC03l8s9" rel="nofollow noreferrer">this</a> paper.</p>

<graph-theory><graph-algorithms><approximation-algorithms><fixed-parameter-tractable>
Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem
advocateofnone
# Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

(Asked by: username_0 on 2022-05-24)

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.

The Shortest Steiner cycle problem is defined as follows:

> Input: An undirected and unweighted graph $G=(V,E)$ and $T\subseteq V$ (called terminals).
>
> Find: Shortest cycle (minimum edges) containing all terminals.

The Shortest $(a,b)-$Steiner path problem is defined as follows:

> Input: An undirected and unweighted graph $G=(V,E)$, $T\subseteq V$ (called terminals) and two specific terminals $a,b \in T$.
>
> Find: Shortest simple path (minimum edges) containing all terminals, which starts at $a$ and ends at $b$.

Are there XP (or even possibly FPT) algorithms known for these related problems, by parameter $k=|T|$?

PS: I could find only a randomized FPT algorithm for the Shortest Steiner cycle problem with runtime $2^{k}n^{\mathcal{O}(1)}$ in [this](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjyuKXy1ff3AhUTuKQKHTiXDewQFnoECCMQAQ&url=https%3A%2F%2Fepubs.siam.org%2Fdoi%2Fpdf%2F10.1137%2F1.9781611973099.139&usg=AOvVaw15HxMpVOkgYwKQYC03l8s9) paper.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, fixed-parameter-tractable

---

## 1 answers

### Answer by username_1 on 2022-05-25. Score: 1 | Accepted answer

Note that you can reduce shortest $(a,b)$-Steiner path to shortest Steiner cycle by adding a terminal vertex of degree 2 adjacent to $a$ and $b$.

If you are asking for derandomization of the Björklund, Husfeldt and Taslaman result, then it can be observed that the problem can be solved in FPT time using $k$-disjoint paths algorithm of Robertson and Seymour as a black box (by fixing an ordering of the terminals one gets a disjoint paths problem). There is also a faster FPT algorithm (still doubly exponential dependency on $k$) given by Kawarabayashi in IPCO 2008.


---

