Constant-Time Algorithms for Sparsity Matroids

This paper discusses constant-time algorithms for sparsity matroids, focusing on (k, l)-sparse and (k, l)-full matroids in graphic representations. It explores properties, testing methods, and graph models like the bounded-degree model. The objective is to efficiently determine if a graph satisfies a property, even in constant time.

• Sparsity Matroids
• Constant-Time Algorithms
• Property Testing
• Bounded-Degree Model
• Graph Representation

tave_641 Follow

Uploaded on Sep 12, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Constant-Time Algorithms for SparsityMatroids Yuichi Yoshida (NII & PFI) Joint with Hiro Ito (UEC) and Shin-ichi Tanigawa (RIMS)

2. Graphic matroid G = (V, E), ? = {F E | F is a forest} ? X Y ? X ? X, Y ?, |X| > |Y| e X \ Y, Y {e} ? Y {e} X Y (E, ?) is called a matroid if the three conditions above hold.

3. Being a forest (1,1)-sparsity F E is called (1, l)-sparse if F F, |F | |V(F )| - 1 not (1,1)-sparse (1,1)-sparse [Claim] Being a forest (1,1)-sparse ? = {F E | F is (1, 1)-sparse} forms a (graphic) matroid.

4. Sparsity matroid F E is called (k, l)-sparse if F F, |F | k|V(F )| - l ?k,l= {F E | F is (k, l)-sparse} forms a matroid. (k, l)-sparsity matroid ?k.l(G) = (E, ?k,l) rankk.l(G) = the rank of ?k.l(G) = max {|F| : F ?k,l}. Ex. rank1,1(G) = the maximum size of a forest in G.

5. Sparsity matroid G is called (k, l)-full if rankk,l(G) = kn l. (k, k)-full contains k edge-disjoint spanning trees (2, 2)-full (2, 3)-full rigid rigid flexible

6. Property testing Motivation: Decide whether a graph G satisfies a property P very efficiently, even in constant time. all graphs P Need to read G completely Can we distinguish more quickly? not P far

7. Property testing G is -far from a property P if we must add or remove at least m edges A tester for P: all functions accept w.p. 2/3 P -far reject w.p. 2/3

8. Graph representation: bounded-degree model [GR02] Only consider graphs with a degree bound d. Given n, d in advance. Get information of G through an oracle OG OG(v, i) = the i-th neighbor of v. v Many properties are known to be testable in constant time. H-freeness, planarity, k-edge-connectivity, etc.

9. Main result [Theorem] 1. We can test (k, l)-fullness in constant time. 2. We can compute rankk.l(G) with additive error n in constant time. (rankk.l(G) = max {|F| : (k, l)-sparse F E}) Query complexity: (d/ )^O(1/ 2)queries ( = / d).

10. Why is this important? Want to characterize constant-time testable properties. Want to know why testable properties are testable. 1. H-freeness testable because of its locality. 2. cycle-freeness, planarity testable because they have separators [HKNO09, NS11] 3. k-edge-connectivity / having a perfect matching no general reason was known. Our intuition: matroid / edge-augmentation help?

11. Proof Sketch

12. Testing k-edge-connectivity [GR02, Ore10] [WN87] To make G k-ec, we need to add maxP X P (k-d(X)) / 2 edges, where P is a sub-partition of V. If G is -far from k-ec, X P (k-d(X)) / 2 n. |P| = (n) (n) constant-size parts X P satisfy d(X) < k. X d(X)

13. Testing (k, k)-fullness [NW61] To make G (k, k)-full, we need to add -k + maxP X P (k-d(X) / 2) edges, where P is a partition of V. Ex. k = 2, G = 3-regular expander Very far from (2, 2)-fullness. But no local witness exists. (n) lower bound for one-sided error testers.

14. Key idea Compute rankk.l(G) with additive error n in constant time. 1. Consider a graph G (in mind) obtained by removing redundant edges from small ?k,l(G)-components rankk,l(G) = rankk,l(G ) rankk,0(G ) 2. Give an oracle access to OG using OG . 3. rankk,0(G ) = the largest size of k e.d. pseudoforests. Can be computed in constant time via maximum matching [NO08, YYI09].

15. Remove redundant edges from ?1,1-components ?1,1-component = bridge or bi-connected component. rank1,1(G) = rank1,1(F1) F3 F1 + rank1,1(F2) + rank1,1(F3) F2 Take a spanning tree in each component. rank1,1(F1 ) = rank1,1(F1) rank1,1(F2 ) = rank1,1(F2) rank1,1(F3 ) = rank1,1(F3) rank1,1(G ) = rank1,1(G) F3 F1 F2

16. Remove redundant edges from ?1,1-components For each component F, rank1,1(F) rank1,0(F) |V(F)| - 1 = rank1,1(F) rank1,1(G ) = rank1,0(G ) F To give an oracle access to G in constant time, we only preprocess small ?1,1-components. rank1,1(G ) rank1,0(G )

17. Other results (k, l)-ec orientability is testable in constant time. r (k, l)-ec-o: orientation v, k ed-paths from r to v l ed-paths from v to r Unifies sparsity and edge-connectivity (k, 0)-ec-orientable (k, k)-full (k, k)-ec-orientable 2k-ec

18. Open Problems Constant-time algorithms for other problems related to matroids? matroid intersection matroid parity Characterizing constant-time testable properties. Locality, separators and matroids / edge-augmentation. How can we unify them?

20. Remove redundant edges from small ?1,1-component F is ?1,1-component V(F) is bi-connected or an edge. large small rank1,1(G) Take spanning trees in small components. = rank1,1(G )

21. Compute rankk,0(G) Computing rankk,0(G ) amounts to finding F E such that there is one-to-one correspondence between V and F. Can be done by computing the maximum size of a matching in an auxiliary graph. Use existing works [NO08, YYI09].