Beyond Classes of Graphs with "Few" Minimal Separators: FPT Results Through Potential Maximal Cliques
Liedloff
M
author
Montealegre
P
author
Todinca
I
author
2019
English
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 XFV 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 Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly 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 Gpoly+kv, with parameter k, if the modulator is also part of the input.
FPT algorithms
Treewidth
Potential maximal cliques
WOS:000460105700003
exported from refbase (show.php?record=989), last updated on Fri, 31 May 2019 22:08:13 -0400
text
10.1007/s00453-018-0453-2
Liedloff_etal2019
Algorithmica
Algorithmica
2019
Springer
continuing
periodical
academic journal
81
3
986
1005
0178-4617