## Abstract

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 language | English |
---|---|

Pages (from-to) | 986-1005 |

Number of pages | 20 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 3 |

DOIs | |

State | Published - 15 Mar 2019 |

Externally published | Yes |

## Keywords

- FPT algorithms
- Potential maximal cliques
- Treewidth