论文标题
有限树深度的平均游戏
Parity Games of Bounded Tree-Depth
论文作者
论文摘要
解决平等游戏的确切复杂性是一个主要的开放问题。几位作者已经在特定的图形类别上搜索了有效的算法。尤其是，Obdržálek表明，对于有界树宽度或集团宽度的图形，问题是在$ \ mathrm {p} $中，后来由Ganardi改进了Ganardi，后者证明它甚至在$ \ Mathrm {Logcfl} $中（对于Clique-Fitth案例中还有一个额外的假设）。在这里，我们通过显示有界树深度图的图表来扩展这一研究线，求解平等游戏的问题在Logspace统一$ \ text {ac}^0 $中。我们首先考虑了我们从集团宽度的修改中获得的参数来实现这一目标，我们将其称为浅层集团宽度。随后，我们提供合适的还原。
The exact complexity of solving parity games is a major open problem. Several authors have searched for efficient algorithms over specific classes of graphs. In particular, Obdržálek showed that for graphs of bounded tree-width or clique-width, the problem is in $\mathrm{P}$, which was later improved by Ganardi, who showed that it is even in $\mathrm{LOGCFL}$ (with an additional assumption for clique-width case). Here we extend this line of research by showing that for graphs of bounded tree-depth the problem of solving parity games is in logspace uniform $\text{AC}^0$. We achieve this by first considering a parameter that we obtain from a modification of clique-width, which we call shallow clique-width. We subsequently provide a suitable reduction.
