Finding Optimal Triangulations Parameterized by Edge Clique Cover.

Many graph problems can be formulated as a task of finding an optimal triangulation of a given graph with respect to some notion of optimality. In this paper we give algorithms to such problems parameterized by the size of a minimum edge clique cover ($cc$) of the graph. The parameter $cc$ is both natural and well-motivated in many problems on this setting. For example, in the perfect phylogeny problem $cc$ is at most the number of taxa, in fractional hypertreewidth $cc$ is at most the number of hyperedges, and in treewidth of Bayesian networks $cc$ is at most the number of non-root nodes of the Bayesian network. Our results are based on the framework of potential maximal cliques. We show that the number of minimal separators of graphs is at most $2^{cc}$ and the number of potential maximal cliques is at most $3^{cc}$. Furthermore, these objects can be listed in times $O^*(2^{cc})$ and $O^*(3^{cc})$, respectively, even when no edge clique cover is given as input; the $O^*(\cdot)$ notation omits factors polynomial in the input size. Using these enumeration algorithms we obtain $O^*(3^{cc})$ time algorithms for problems in the potential maximal clique framework, including for example treewidth, minimum fill-in, and feedback vertex set. We also obtain an $O^*(3^m)$ time algorithm for fractional hypertreewidth, where $m$ is the number of hyperedges. In the case when an edge clique cover of size $cc'$ is given as an input we further improve the time complexity to $O^*(2^{cc'})$ for treewidth, minimum fill-in, and chordal sandwich. This implies an $O^*(2^n)$ time algorithm for perfect phylogeny, where $n$ is the number of taxa. We also give polynomial space algorithms with time complexities $O^*(9^{cc'})$ and $O^*(9.001^{cc})$ for problems in this framework.