Testing Hamiltonicity (and other problems) in Minor-Free Graphs
Testing Hamiltonicity (and other problems) in Minor-Free Graphs
复制标题
在无次要图中测试哈密顿性（和其他问题）
DOI：
10.4230/lipics.approx/random.2021.61
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nadav Shoshan
中科院分区：
文献类型：
--
作者：
Reut Levi;Nadav Shoshan
在本文中，我们提供了几个基本问题的次线性算法的设置，其中输入图排除了一个固定的小，即，这是一个minor-free graph。特别是，我们提供了以下算法的minor-free无界度图。我们的两种算法都使用分区预言机，这是Hassidim等人（FOCS 2009）引入的一种工具，它提供对图的分区的访问，使得切割边的数量很小，并且分区的每个部分都很小。我们的算法的多项式依赖在1 /1/2中是通过结合Kumar-Seshadhri-Stolman（ECCC 2021）最近的poly（d/2）-查询划分预言来实现的，该预言针对度由d限定的无次图。对于有界度的minor-free图，我们引入了覆盖划分预言机的概念，它是划分预言机的一个放松版本，并为这类图设计了一个poly（d/n）-时间覆盖划分预言机.使用我们的覆盖划分预言，我们提供了与上面相同的结果（除了汉密尔顿性的测试者有单侧误差），对于无次子的有界度图，以及表明任何单调和可加性的属性（例如二分性）可以通过进行poly（d/n）-查询在无次子的图中进行测试。在我们的算法中使用覆盖分区预言机而不是分区预言机的好处是它的简单性和在获得的查询复杂度中的1 /2多项式依赖性的改进。
In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs. Both our algorithms use partition oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1 /ϵ of our algorithms is achieved by combining the recent poly( d/ϵ )-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d . For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly( d/ϵ )-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one-sided error) for minor-free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly( d/ϵ )-queries. The benefit using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1 /ϵ in the obtained query complexity.
登录
查看更多内容
在生成树附近建造，很少进行局部检查
影响因子：
1
作者：
Levi, Reut;Moshkovitz, Guy;Ron, Dana;Rubinfeld, Ronitt;Shapira, Asaf
通讯作者：
Shapira, Asaf
Spanner 的本地计算算法
DOI：
--
发表时间：
2019
期刊：
Innovations in Theoretical Computer Science (ITCS
影响因子：
--
作者：
Parter, Merav;Rubinfeld, Ronitt;Vakilian, Ali;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak
稀疏生成图的局部算法
影响因子：
1.1
作者：
Levi, Reut;Ron, Dana;Rubinfeld, Ronitt
通讯作者：
Rubinfeld, Ronitt
平面图：随机游走和二分测试
DOI：
10.1109/focs.2011.69
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Czumaj A
通讯作者：
Czumaj A