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

Abstract

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.