(Piotr reports on the last two talks of Day 4.)

After lunch, Christian Sohler served new results on property testing in hyperfinite graphs. A family of graphs is (k,\epsilon)-hyperfinite if in any graph we can remove \epsilon n edges to obtain connected components of size at most k. For example, by planar separator theorem, planar graphs qualify for this distinction. In the talk, Christian focused on graphs of bounded degree and k.

Christian presented a number of results, including the following (and surprising) one: every property is testable on hyperfinite graphs. The basic idea is: for any graph G in the family, if we remove some \epsilon n edges from G, then the resulting graph G’ can be fully described as a distribution over graphs of size at most k and one can approximate this distribution by random sampling. One interesting implication of his work is that computing statistics of “graph motifs” in large networks (a popular tool in network analysis) is justified, since such statistics identify the graph itself.

The final talk of the day was by Oded Goldreich, who talked about sub-linear algorithms in graphs of bounded degree. He considered a model where one can ask for a specific (i.e., the i-th) neighbor of a given node. He considered the problem of *finding* (not just testing existence of) cycles and trees in a given graph. The first of them was a (roughly) \sqrt{N}-time algorithm for finding cycles in N-vertex graphs that are eps-far from being cycle free. One can also generalize this result to finding cycles of length at least k, for a fixed k. He also showed that one cannot do (much) better than \sqrt{N} is optimal. In contrast, he also gave constant time algorithms for finding trees of size at least k (for constant k).

The algorithms are based on the following observation linking one-sided property testing and finding structures with that property. Specifically, if such tester rejects a graph, it must have some “evidence” that the property does not hold. E.g., if we test for bipartiteness, then the violating structure is a non-bipartite graph. This leads to an algorithm that finds a desired structure.

To obtain an algorithm for finding cycles (or testing cycle freeness), he used a reduction to bipartite-ness testing. The idea is simple and very cute: for each each edge one replaces it by a 2-path with prob. 1/2, and keeps it intact otherwise. Clearly, any cycle-free graph is mapped into a cycle-free (and therefore bipartite) graph. The key observation is that a graph that is far from being cycle free is mapped into a graph that is far from being bipartite.

Advertisements