论文标题
普通树中当地可检查问题的有效分类
Efficient Classification of Locally Checkable Problems in Regular Trees
论文作者
论文摘要
我们提供了实用，有效的算法，这些算法会在两个设置中自动确定$ [θ（\ log n），θ（n）] $区域中给定的本地可检查图问题的渐近分布式圆形复杂性。我们提出了一种无根据的普通树和另一种算法的算法，用于生根的常规树。该算法将当地可检查的标签问题描述为输入，并且运行时间在问题描述的大小上是多项式。该算法决定该问题是否可以在$ O（\ log n）$ rounds中解决。如果没有，众所周知，对于某些$ k = 1、2，\ dotsc $，复杂性必须为$θ（n^{1/k}）$，在这种情况下，算法还输出了指数$ k $的正确值。 在$ o（\ log n）$ case中的根树中，我们可以通过使用先前工作的算法进一步确定精确的复杂性类；对于未根的树，在$ O（\ log n）$区域中更细粒度的分类仍然是一个悬而未决的问题。
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)]$ region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in $O(\log n)$ rounds. If not, it is known that the complexity has to be $Θ(n^{1/k})$ for some $k = 1, 2, \dotsc$, and in this case the algorithms also output the right value of the exponent $k$. In rooted trees in the $O(\log n)$ case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the $O(\log n)$ region remains an open question.
