We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ($cc$) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., 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. We show that the number of minimal separators of graphs is at most $2^{cc}$, the number of potential maximal cliques is at most $3^{cc}$, and 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. These enumeration algorithms imply $O^*(3^{cc})$ time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give $O^*(4^m)$ time and $O^*(3^m)$ time algorithms, respectively, where $m$ is the number of hyperedges. When an edge clique cover of size $cc'$ is given as a part of the input we give $O^*(2^{cc'})$ time algorithms 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^{cc + O(\log^2 cc)})$ for problems in this framework.
翻译:我们考虑的问题可以被表述为找到一个最优化的图形 w.r.t. 的三角方程( cccth) 。 我们将算法参数以最小边缘 cluque cloque cover 的大小( cc$ cc$ ) 来表示这些问题。 在这种环境下, 这个参数自然出现在许多问题中, 例如在完美的血压问题中 $cc$ 最多是分类数, 分数超树基$最多是超级基数, 在Bayesian 网络的树枝中, $ cc$ 最多是非根端节节节点 。 我们显示, 最小的图表分离器数目最多是 $% cc美元 美元, 这些对象可以以 $% ( cccc} 美元) 和 $% ( cc% 美元) 的时间值 来表示时间值, 即便没有给出边缘值作为输入值 ; 美元 (c) 美元 美元 和 美元 平面值 时间值 的计算数也是 。