Getting linear time in graphs of bounded neighborhood diversity

Parameterized complexity, introduced to efficiently solve NP-hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity ((Formula presented.)) for several graph theoretic problems in (Formula presented.) : Maximum (Formula presented.) -Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular-width ((Formula presented.)) and consequently—as (Formula presented.) is a special case of (Formula presented.) —by (Formula presented.). However, the proposed novel algorithms allow for improving the computational complexity from time (Formula presented.) —where (Formula presented.) and (Formula presented.) denote, respectively, the number of vertices and edges in the input graph—to time (Formula presented.) which is only additive in the size of the input. Then we consider some classical NP-hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.