<p>The problem formulation is as follows:</p>
<blockquote>
<p>Input: Undirected graph <span class="math-container">$G=(V,E)$</span>, a set of vertices <span class="math-container">$S\subseteq |V|$</span>, a weight function <span class="math-container">$w:E\to \mathbb{R}$</span> and a threshold <span class="math-container">$T\in \mathbb{R}$</span>.</p>
<p>Parameter: <span class="math-container">$|S|=k$</span>.</p>
<p>Problem: decide whether there exist in <span class="math-container">$G$</span> a simple cycle going through <span class="math-container">$S$</span>'s vertices and it's weight is <span class="math-container">$\leq T$</span>.</p>
</blockquote>
<p>Andreas Bjorklund et al. <a href="http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf" rel="nofollow noreferrer">gave a <span class="math-container">$O^*(2^k)$</span> algorithm</a> for finding the shortest simple cycle through <span class="math-container">$k$</span> vertices (i.e. in this setting <span class="math-container">$\forall e:w(e)=1$</span>).</p>
<p>Can this result be extended (or is there other known result) for finding a minimum weight cycle through <span class="math-container">$k$</span> vertices (for a weighted graph) in <span class="math-container">$FPT$</span> time?</p>

CC BY-SA 3.0
2014-04-03T13:41:49.673Z
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
CC BY-SA 3.0
2014-04-03T16:55:25.670Z
For both a simpler algorithm and analysis, see http://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
<cc.complexity-theory><graph-algorithms><parameterized-complexity><fixed-parameter-tractable>
Is minimum weight simple cycles through specified vertics fixed parameter tractable?
R B
# Is minimum weight simple cycles through specified vertics fixed parameter tractable?

(Asked by: username_0 on 2014-04-02)

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](http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf) 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?

**Tags:** cc.complexity-theory, graph-algorithms, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_2**: For both a simpler algorithm and analysis, see http://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.  

---

## 0 answers

