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

Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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.

Original languageEnglish
Pages (from-to)986-1005
Number of pages20
Issue number3
StatePublished - 15 Mar 2019
Externally publishedYes


  • FPT algorithms
  • Potential maximal cliques
  • Treewidth


Dive into the research topics of 'Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques'. Together they form a unique fingerprint.

Cite this