Fast distributed algorithms for testing graph properties
Fast distributed algorithms for testing graph properties
复制标题
用于测试图属性的快速分布式算法
作者：
K. Censor;E. Fischer;Gregory Schwartzman;Y. Vasudev
针对拥塞模型中属性测试的逼近问题，我们对分布式属性测试生成算法进行了深入的研究。特别是，对于所谓的稠密图测试模型，我们对几乎所有具有单边测试的图的性质进行了仿真测试，而在一般模型中，我们得到了更快的无三角形和无圈测试，在稀疏模型中，我们得到了更快的二部性测试。此外，我们还给出了检验二部性和无圈性的对数下界，即使在较强的局部模型下也是成立的。在大多数情况下，在并行性的帮助下，分布式算法的运行时间比传统性能测试的顺序查询模型要短得多。更重要的是，我们开发的用于测试图形属性的分布式算法在许多情况下比已知的准确确定属性是否成立的算法要快得多。最简单的属性测试算法允许相对平稳地过渡到分布式模型。对于更复杂的任务，我们开发了可能独立感兴趣的新机制。
We initiate a thorough study of distributed property testing—producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called dense graph testing model we emulate sequential tests for nearly all graph properties having 1-sided tests, while in the general model we obtain faster tests for triangle-freeness and cycle-freeness, and in the sparse model we obtain a faster test for bipartiteness. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness, which holds even in the stronger LOCAL model. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time than their counterparts from the sequential querying model of traditional property testing. More importantly, the distributed algorithms we develop for testing graph properties are in many cases much faster than what is known for exactly deciding whether the property holds. The simplest property testing algorithms allow a relatively smooth transition to the distributed model. For the more complex tasks we develop new machinery that may be of independent interest.