In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover ($\operatorname{ vc}$) and modular width ($\operatorname{ mw}$). We prove that for any graph, the number of minimal separators is $\mathcal{ O}^*(3^{ \operatorname{ vc}})$ and $\mathcal{ O}^*(1.6181^{ \operatorname{ mw}})$, and the number of potential maximal cliques is $\mathcal{ O}^*(4^{ \operatorname{ vc}})$ and $\mathcal{ O}^*(1.7347^{ \operatorname{ mw}})$, and these objects can be listed within the same running times. (The $\mathcal{ O}^*$ notation suppresses polynomial factors in the size of the input.) Combined with known results, we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time $\mathcal{ O}^*(4^{ \operatorname{ vc}})$ or $\mathcal{ O}^*(1.7347^{ \operatorname{ mw}})$.
Categories: cs.DS