- graph-theory graph-algorithms approximation-algorithms fixed-parameter-tractable
- Updated Wed, 15 Jun 2022 10:22:22 GMT

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.

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.

External links referenced by this document: