Theoretical Computer Science

# Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem

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

## Solution

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 Bjrklund, 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.