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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Saeed Apr 3 '14 at 13:41
  • 2
    $\begingroup$ 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. $\endgroup$ – Andreas Björklund Apr 3 '14 at 16:55

Your Answer

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

Browse other questions tagged or ask your own question.