0
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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