论文标题
解决通过单指数时间和多项式空间中TreeDepth参数参数的连接性问题
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space
论文作者
论文摘要
Cygan等人的突破结果。 （FOCS 2011）表明，通过树宽参数参数的连接性问题可以比以前最著名的时间$ \ Mathcal {o}^*（2^{\ Mathcal {O}（TW \ log（TW \ log（TW）}））$快得多。使用他们的启发的\＆计数技术，他们获得了许多此类问题的$ \ Mathcal {O}^*（α^{TW}）$ TIME算法。此外，假设有强大的指数时间假设，他们证明了这些运行时间是最佳的。不幸的是，像树分解上的其他动态编程算法一样，这些算法也需要指数空间，并且人们认为这是不可避免的。相反，对于称为TreeDepth的稍大较大的参数，已经有几个算法的示例符合匹配树宽的时间边界，但仅使用多项式空间。然而，这对连通性问题仍然开放。 在目前的工作中，我们通过将cut \＆Count技术应用于小型Treedeppth的图来缩小这一知识差距。尽管总体想法没有变化，但我们必须设计新的程序，以始终使用多项式空间计数候选解决方案。具体而言，我们获得了时间$ \ MATHCAL {O}^*（3^d）$和多项式空间，用于连接的顶点封面，反馈顶点集，而在TreeDeppth $ d $的图上，steiner树和Steiner树。同样，我们获得时间$ \ Mathcal {O}^*（4^d）$和用于连接的主导集和连接的奇数transersal的多项式空间。
A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time $\mathcal{O}^*(2^{\mathcal{O}(tw \log(tw))})$. Using their inspired Cut\&Count technique, they obtained $\mathcal{O}^*(α^{tw})$ time algorithms for many such problems. Moreover, they proved these running times to be optimal assuming the Strong Exponential-Time Hypothesis. Unfortunately, like other dynamic programming algorithms on tree decompositions, these algorithms also require exponential space, and this is widely believed to be unavoidable. In contrast, for the slightly larger parameter called treedepth, there are already several examples of algorithms matching the time bounds obtained for treewidth, but using only polynomial space. Nevertheless, this has remained open for connectivity problems. In the present work, we close this knowledge gap by applying the Cut\&Count technique to graphs of small treedepth. While the general idea is unchanged, we have to design novel procedures for counting consistently cut solution candidates using only polynomial space. Concretely, we obtain time $\mathcal{O}^*(3^d)$ and polynomial space for Connected Vertex Cover, Feedback Vertex Set, and Steiner Tree on graphs of treedepth $d$. Similarly, we obtain time $\mathcal{O}^*(4^d)$ and polynomial space for Connected Dominating Set and Connected Odd Cycle Transversal.
