# Is minimum weight simple cycles through specified vertics fixed parameter tractable?

The problem formulation is as follows:

Input: Undirected graph $$G=(V,E)$$, a set of vertices $$S\subseteq |V|$$, a weight function $$w:E\to \mathbb{R}$$ and a threshold $$T\in \mathbb{R}$$.

Parameter: $$|S|=k$$.

Problem: decide whether there exist in $$G$$ a simple cycle going through $$S$$'s vertices and it's weight is $$\leq T$$.

Andreas Bjorklund et al. gave a $$O^*(2^k)$$ algorithm for finding the shortest simple cycle through $$k$$ vertices (i.e. in this setting $$\forall e:w(e)=1$$).

Can this result be extended (or is there other known result) for finding a minimum weight cycle through $$k$$ vertices (for a weighted graph) in $$FPT$$ time?

• I took a brief look at their paper, in their dynamic programming part they compute $F$ function for particular walk, and the key idea is using concatenation to have something like $f(uv)F(v...u)$, that means if you replace $f$ value with weight, doesn't change anything (I mean is still FPT), but I'm not sure whether this algorithm still provides shortest cycle or not (sure if provides a cycle less than given length $l$ then that cycle is less than $l$, but it does not guarantee that if it doesn't find it then there is no such a cycle). But sure if weights are in $N$ then it is pseudo-FPT. – Saeed Apr 3 '14 at 13:41
• For both a simpler algorithm and analysis, see arxiv.org/abs/1301.1517. However, this algorithm and the algorithm you cite can only handle integer weights less than $M$ in $poly(n, \log M)M2^k$ time. – Andreas Björklund Apr 3 '14 at 16:55