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?
Is minimum weight simple cycles through specified vertics fixed parameter tractable?
cc.complexity theory;graph algorithms;parameterized complexity;fixed parameter tractable