  Parameterized complexity theory has enabled a refined classification of the
difficulty of NP-hard optimization problems on graphs with respect to key
structural properties, and so to a better understanding of their true
difficulties. More recently, hardness results for problems in P were achieved
using reasonable complexity theoretic assumptions such as: Strong Exponential
Time Hypothesis (SETH), 3SUM and All-Pairs Shortest-Paths (APSP). According to
these assumptions, many graph theoretic problems do not admit truly
subquadratic algorithms, nor even truly subcubic algorithms (Williams and
Williams, FOCS 2010 and Abboud, Grandoni, Williams, SODA 2015). A central
technique used to tackle the difficulty of the above mentioned problems is
fixed-parameter algorithms for polynomial-time problems with polynomial
dependency in the fixed parameter (P-FPT). This technique was introduced by
Abboud, Williams and Wang in SODA 2016 and continued by Husfeldt (IPEC 2016)
and Fomin et al. (SODA 2017), using the treewidth as a parameter. Applying this
technique to clique-width, another important graph parameter, remained to be
done. In this paper we study several graph theoretic problems for which
hardness results exist such as cycle problems (triangle detection, triangle
counting, girth, diameter), distance problems (diameter, eccentricities, Gromov
hyperbolicity, betweenness centrality) and maximum matching. We provide
hardness results and fully polynomial FPT algorithms, using clique-width and
some of its upper-bounds as parameters (split-width, modular-width and
$P\_4$-sparseness). We believe that our most important result is an ${\cal
O}(k^4 \cdot n + m)$-time algorithm for computing a maximum matching where $k$
is either the modular-width or the $P\_4$-sparseness. The latter generalizes
many algorithms that have been introduced so far for specific subclasses such
as cographs, $P\_4$-lite graphs, $P\_4$-extendible graphs and $P\_4$-tidy
graphs. Our algorithms are based on preprocessing methods using modular
decomposition, split decomposition and primeval decomposition. Thus they can
also be generalized to some graph classes with unbounded clique-width.
