  A linear arrangement (LA) is an assignment of distinct integers to the
vertices of a graph. The cost of an LA is the sum of lengths of the edges of
the graph, where the length of an edge is defined as the absolute value of the
difference of the integers assigned to its ends. For many application one hopes
to find an LA with small cost. However, it is a classical NP-complete problem
to decide whether a given graph $G$ admits an LA of cost bounded by a given
integer. Since every edge of $G$ contributes at least one to the cost of any
LA, the problem becomes trivially fixed-parameter tractable (FPT) if
parameterized by the upper bound of the cost. Fernau asked whether the problem
remains FPT if parameterized by the upper bound of the cost minus the number of
edges of the given graph; thus whether the problem is FPT ``parameterized above
guaranteed value.'' We answer this question positively by deriving an algorithm
which decides in time $O(m+n+5.88^k)$ whether a given graph with $m$ edges and
$n$ vertices admits an LA of cost at most $m+k$ (the algorithm computes such an
LA if it exists). Our algorithm is based on a procedure which generates a
problem kernel of linear size in linear time for a connected graph $G$. We also
prove that more general parameterized LA problems stated by Serna and Thilikos
are not FPT, unless P=NP.
