Before revision:  Despite these efforts, it is a major open problem whether there exists a linear-time O(f(k)(| E | + | V |)) parameterized algorithm . We present here two significant results in this direction. First, we obtain an O(  | E| + k^2| V| \log{|V|)-time algorithm, which in particular is faster than all existing MPC algorithms when k = o(\sqrt{|V|}/\log{|V|}) and |E| = \omega(k|V|) but |E| = o(|V|^2).
After revision:  Despite these efforts, it is a major open problem whether there exists a linear-time O(f(k)(| E | + | V |)) parameterized algorithm computing the width. We answer this question affirmatively by presenting an O( | E| + k^2| V| \log{|V|)-time algorithm, which in particular is faster than all existing MPC algorithms when k = o(\sqrt{|V|}/\log{|V|}) and |E| = \omega(k|V|) but |E| = o(|V|^2).