Overview of Subgraph Testing Model: Insights & Focus
The Subgraph Testing Model by Oded Goldreich & Dana Ron, focusing on property testing & its application in query complexity. Discover the standard error definitions & the new model testing properties of subgraphs, along with initial observations and comparisons with the bounded-degree graph model.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
The Subgraph Testing Model Oded Goldreich Weizmann Institute of Science Joint work with Dana Ron.
Property Testing: informal definition A relaxation of a decision problem: For a fixed property P and any given object O, determine whether O has property P or is far from having property P (i.e., O is far from any other object having P). Objects viewed as functions. Inspecting = querying the function/oracle. ? ? ? ? ? Focus: sub-linear time algorithms = performing the task by inspecting the object at few locations.
Property Testing: the standard (one-sided error) defn A property P P = nP Pn, where P Pnis a set of functions with domain Dn. The tester T gets explicit input n and , and oracle access to a function f with domain Dn. If f P Pnthen Prob[Tf(n, ) accepts] = 1 (or > 2/3). If f is -far from P Pnthen Prob[Tf(n, ) rejects] > 2/3. (Distance is defined as fraction of disagreements.) Focus: Focus: query complexity query complexity, , q(n, ) |Dn| Special focus Special focus: : q(n, )=q( ), independent of n. Terminology: Terminology: is called the is called the proximity proximity parameter. parameter.
The new model: Testing properties of subgraphs For a fixed base graph G=(V,E), let P PGbe a set of Boolean functions with domain E representing a set of subgraphs of G. The tester T gets explicit input G=(V,E) and , and oracle access to a function f:E If f P PGthen Prob[Tf(G, ) accepts] = 1 (or > 2/3). If f is -far from P PGthen Prob[Tf(G, ) rejects] > 2/3. (Distance is defined as fraction of disagreements.) 0,1 . Focus: Focus: query complexity query complexity, , q(G, ) |E| Special focus Special focus: : q(G, )=q( ), independent of G. Terminology: Terminology: is called the is called the proximity proximity parameter. parameter.
Initial observations and actual focus The tester T gets explicit (based graph) input G=(V,E) and , and oracle access to a function f:E If f P PGthen Prob[Tf(G, ) accepts] = 1 (or > 2/3). If f is -far from P PGthen Prob[Tf(G, ) rejects] > 2/3. (Distance is defined as fraction of disagreements.) 0,1 . The dense graph model is a special case (on input n, let G = n-vertex clique). Testing Boolean functions is a special case (on input n, let G = n-vertex augmented path). Focus: Focus: The base graph G has bounded-degree. Compare the complexity of testing properties of subgraphs to complexity in the BDG model.
Background: the bounded-degree graph (BDG) model For a fixed d, we consider properties of graphs of max. degree d, represented by their incidence function. An n-vertex graph is represented by g:[n] [d] such that g(v,i) is the ithneighbor of v (and g(v,i)=0 if v has less than I neighbors). The tester T gets explicit input n and , and oracle access to a function g representing an n-vertex graph. If f P Pnthen Prob[Tf(n, ) accepts] = 1 (or > 2/3). If f is -far from P Pnthen Prob[Tf(n, ) rejects] > 2/3. (Distance is defined as fraction of disagreements.) [n] 0
Results (sample): Downward Monotone Properties Downwards monotone = Preserved under omission of edges. Thm1: If a down.mono. is testable within query complexity Qd( ,n) in the BDG model, then, for every n-vertex graph G of degree d, testing whether a subgraph of G is in can be done in query complexity Qd( /d,n). Note: If G , then all subgraphs are in (i.e., testing is trivial). Thm2: For c some base graphs is as hard as testing c-colorability in the BDG model; that is, (n) for c=3, and (n1/2) for c=2 and =1/polylog(n). 2,3 , testing c-colorability of subgraphs of Take home msg (from Thms 1 & 2): Testing subgraphs in never harder than testing in BDG model, but it may be just as hard.
Results (sample): Non-Downward Monotone Properties Thm3 (testing subgraphs may be harder than in the BDG): There exist (upwards mono.) that is testable within complexity poly(1/ ) in the BDG model; but, for some bounded-degree n-vertex graph G, testing whether a subgraph of G is in requires (loglog(n)) queries. Thm4: For every bounded-degree graph, connectivity of subgraphs can be tested using poly(1/ ) queries. Note: The bound in Thm4 matches the bound in the BDG model. Open: What about 2-connectivity?
Results (more): Non-Downward Monotone Propoerties Thm5: Let be a locally characterizable property (i.e., it can be expressed as conjunction of constraints on O(1)-neighborhoods) and suppose that the base graph G is outerplanar. Then, we can test whether the subgraph of G is in using O( -1log(n)) queries. Note: Generalizes to base graphs with O(1)-size separators. Open Problems: 1. Can this be improved to poly(1/ )? How about testing regularity or even just 1-regularity (which means perfect-matching)? 2. What about testing regularity (or just 1-regularity) when the base graph G is a (two-dim) grid? 3. What about testing if the subgraph is Eulerian? Can do it in poly(1/ ) time when G is a grid, but what about any base graph?
A kind of partial summary Sometimes (e.g., for all Down. Mono. properties) testing in the subgraph model is not harder than in the BDG model, and sometimes they are not easier. Sometimes (e.g., Thm3), testing in the subgraph model is harder than in the BDG model, and sometimes they are easier for some base graphs (e.g., trivial cases). Open: Can testing subgraphs be easier for any base graph? Yes, if the property is allowed to depend on the degree bound in the BDG model (i.e., contains only d-regular graphs).
We have introduced a new model, presented a few results, and posed many open problem. END Slides available at http://www.wisdom.weizmann.ac.il/~oded/T/subgraph.pptx Paper available at http://www.wisdom.weizmann.ac.il/~oded/p_subg.html
Property Testing (super-fast approximate decision): an illustration Gothic cathedral ? One Motivation: Real objects are far apart. Other motivations: Approx. per se, or a preliminary step. Deciding by inspecting few locations in the object.
