Constant-time algorithms for sparsity matroids. Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS7391
Constant-time algorithms for sparsity matroids. Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS7391
复制标题
稀疏拟阵的恒定时间算法。
DOI：
10.1007/978-3-642-31594-7_42
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Shin-ichi Tanigawa and Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Hiro Ito;Shin-ichi Tanigawa and Yuichi Yoshida
graphG = (V, E) (k,ℓ)F -简约如果| | |≤k V (F) |−ℓ为anyF⊆EwithF≠∅。这里，V(F)表示与toF相关的顶点集合。如果图g = （V，E）包含一个(k, r)-稀疏子图，有|V|个顶点和k|V|−r个边，则称为(k, r)-满。（k, r）-稀疏子图的边集族构成了矩阵1的独立集族，称为g的稀疏矩阵。本文给出了阶有界无向图稀疏矩阵秩的常时间逼近算法。该算法导致有界度模型中(k, r)-丰满的常数时间检验（即，我们可以高概率地确定输入图是否满足属性或远非属性）。根据kand和r的值，我们的算法可以测试图的各种属性，如连通性、刚性以及可以以统一的方式打包多少棵生成树。在此基础上，我们还提出了有界度模型中(k, r)-边连通可定向性的常时间检验方法，其中无向图gis称为(k, r)-边连通可定向，如果有一个顶点∈v的g的取向包含从每个顶点v∈v到每个顶点v∈v的不相交的路径和从每个顶点v∈v到每个顶点v∈v的不相交的路径。如果一个测试器总是接受满足p的图，那么它就被称为片面误差测试器。我们证明，对于任意k≥2和（固有）r≥0，对于(k, r) -完备性和(k, r) -边连通定向性，每一个单侧误差检验都需要Ω(n)次查询。
A graphG= (V,E) is called (k, ℓ)-sparse if |F| ≤k|V(F)| − ℓ for anyF⊆EwithF≠ ∅. Here,V(F) denotes the set of vertices incident toF. A graphG= (V,E) is called (k,ℓ)-full ifGcontains a (k,ℓ)-sparse subgraph with |V| vertices andk|V| − ℓ edges. The family of edge sets of (k,ℓ)-sparse subgraphs forms a family of independent sets of a matroid onE, known as the sparsity matroid ofG. In this paper, we give a constant-time algorithm that approximates the rank of the sparsity matroid associated with a degree-bounded undirected graph. This algorithm leads to a constant-time tester for (k,ℓ)-fullness in the bounded-degree model, (i.e., we can decide with high probability whether the input graph satisfies a property or far from it). Depending on the values ofkand ℓ, our algorithm can test various properties of graphs such as connectivity, rigidity, and how many spanning trees can be packed in a unified manner.Based on this result, we also propose a constant-time tester for (k,ℓ)-edge-connected-orientability in the bounded-degree model, where an undirected graphGis called (k,ℓ)-edge-connected-orientable if there exists an orientationofGwith a vertexr∈Vsuch thatcontainskarc-disjoint dipaths fromrto each vertexv∈Vand ℓ arc-disjoint dipaths from each vertexv∈Vtor.A tester is called a one-sided error tester forPif it always accepts a graph satisfyingP. We show, for anyk≥ 2 and (proper) ℓ ≥ 0, every one-sided error tester for (k,ℓ)-fullness and (k,ℓ)-edge-connected-orientability requires Ω(n) queries.