  We study the influence of a graph parameter called modular-width on the time
complexity for optimally solving well-known polynomial problems such as Maximum
Matching, Triangle Counting, and Maximum $s$-$t$ Vertex-Capacitated Flow. The
modular-width of a graph depends on its (unique) modular decomposition tree,
and can be computed in linear time $O(n+m)$ for graphs with $n$ vertices and
$m$ edges. Modular decompositions are an important tool for graph algorithms,
e.g., for linear-time recognition of certain graph classes. Throughout, we
obtain efficient parameterized algorithms of running times $O(f(mw)n+m)$,
$O(n+f(mw)m)$ , or $O(f(mw)+n+m)$ for graphs of modular-width $mw$. Our
algorithm for Maximum Matching, running in time $O(mw^2\log mw \cdot n+m)$, is
both faster and simpler than the recent $O(mw^4n+m)$ time algorithm of Coudert
et al. (SODA 2018). For several other problems, e.g., Triangle Counting and
Maximum $b$-Matching, we give adaptive algorithms, meaning that their running
times match the best unparameterized algorithms for worst-case modular-width of
$mw=\Theta(n)$ and they outperform them already for $mw=o(n)$, until reaching
linear time for $mw=O(1)$.

Data Structures and Algorithms