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

Let \(\mathcal {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 \(\mathcal {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\subseteq F \subseteq V\) such that the treewidth of G[F] is at most t, property \(\mathcal {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, Independent\(\mathcal {H}\)-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 2015) proved that the problem is polynomial on the class of graph \({\mathcal {G}}_{{\text {poly}}}\), i.e. the graphs having at most \({\text {poly}}(n)\) minimal separators for some polynomial \({\text {poly}}\). Here we consider the class \({\mathcal {G}}_{{\text {poly}}}+ kv\), formed by graphs of \({\mathcal {G}}_{{\text {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 \({\mathcal {G}}_{{\text {poly}}}+ kv\), with parameter k, if the modulator is also part of the input.