论文标题
关于TreeDeppth分解的最小分离器的大小
On the Size of Minimal Separators for Treedepth Decomposition
论文作者
论文摘要
TreeDepth分解具有多种实际应用，可用于加快许多参数化算法。有几项旨在设计可伸缩算法以计算精确详细分解的作品。这些包括基于所有最小分离器的作品。在这些算法中，尽管列举了许多最小的分离器，但用于最佳解决方案的最小分离器在经验上非常小。因此，分析最小分离器大小的上限是一个重要的问题，因为它有可能显着减少计算时间。如果$ td（g）= | s | + td（g \ backslash s）$，其中$ td（g）$表示$ g $的treedepepth。然后，我们对最佳顶部分离器的大小有两个理论结果。 （1）对于任何$ g $ \ le 2tw（g）$，其中$ tw（g）$是$ g $的树宽。 （2）对于任何$ c <2 $，都存在图$ g $，以便任何最佳的顶部分隔符$ s $ g $ ak a $ | s | > c \ cdot tw（g）$，即，第一个结果对最佳顶部分离器的大小紧密结合。
Treedepth decomposition has several practical applications and can be used to speed up many parameterized algorithms. There are several works aiming to design a scalable algorithm to compute exact treedepth decompositions. Those include works based on a set of all minimal separators. In those algorithms, although a number of minimal separators are enumerated, the minimal separators that are used for an optimal solution are empirically very small. Therefore, analyzing the upper bound on the size of minimal separators is an important problem because it has the potential to significantly reduce the computation time. A minimal separator $S$ is called an optimal top separator if $td(G) = |S| + td(G \backslash S)$, where $td(G)$ denotes the treedepth of $G$. Then, we have two theoretical results on the size of optimal top separators. (1) For any $G$, there is an optimal top separator $S$ such that $|S| \le 2tw(G)$, where $tw(G)$ is the treewidth of $G$. (2) For any $c < 2$, there exists a graph $G$ such that any optimal top separator $S$ of $G$ have $|S| > c \cdot tw(G)$, i.e., the first result gives a tight bound on the size of an optimal top separator.
