Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques

Let P(G, X) be a property associating a boolean value to each pair (G, X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G= (V, E) , find subsets X⊆ F⊆ V such that the treewidth of G[F] is at most t, property P(G[F] , X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 2015) proved that the problem is polynomial on the class of graph G _poly , i.e. the graphs having at most poly (n) minimal separators for some polynomial poly. Here we consider the class G _poly + kv, formed by graphs of G _poly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on G _poly + kv, with parameter k, if the modulator is also part of the input.