Transcript Testing Expansion in Bounded Degree Graphs

University of Dortmund
Testing Expansion in Bounded
Degree Graphs
Christian Sohler
University of Dortmund
(joint work with Artur Czumaj,
University of Warwick)
Christian Sohler
1
University of Dortmund
Testing Expansion in Bounded Degree Graphs
Introduction
Property Testing[Rubinfeld, Sudan]:
• Formal framework to analyze „Sampling“-algorithms for
decision problems
• Decide with help of a random sample whether a given object
has a property or is far away from it
Close to
property
Property
Far away from
property
Christian Sohler
2
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Property Testing[Rubinfeld, Sudan]:
• Formal framework to analyze „Sampling“-algorithms for
decision problems
• Decide with help of a random sample whether a given object
has a property or is far away from it
Definition:
• An object is e-far from a property P, if it differs in more than an
e-fraction of ist formal description from any object
with property P.
Christian Sohler
3
University of Dortmund
Testing Expansion in Bounded Degree Graphs
Introduction
Bounded degree graphs
•
•
•
•
•
Graph (V,E) with degree bound d
V={1,…,n}
Edges as adjacency lists through function f: V {1,…,d} V
f(v,i) is i-th neighbor of v or ■, if i-th neighbor does not exist
Query f(v,i) in O(1) time
d
1
2
4
2
4
1
3
4
■
4
2
3
■
■
■
1
1
3
2
4
n
Christian Sohler
4
University of Dortmund
Testing Expansion in Bounded Degree Graphs
Introduction
Definition:
• A graph (V,E) with degree bound d and n vertices is e-far from
a property P, if more than edn entries in the adjacency lists
have to be modified to obtain a graph with property P.
Example (Bipartiteness):
d
1
2
4
2
4
1
3
4
■
4
2
3
■
■
■
1
n
1
3
2
4
1/7-far from bipartite
Christian Sohler
5
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Goal:
• Accept graphs that have property P with probability
at least 2/3
• Reject graphs that are e-far from P with probability
at least 2/3
Complexity Measure:
• Query (sample) complexity
• Running time
Christian Sohler
6
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Definition [Neighborhood]
• N(U) denotes the neighborhood of U, i.e.
N(U) = {vV-U:  uU such that (v,u)E}
Definition [Expander]:
• A Graph is an a-Expander, if N(U) a|U| for each UV with
|U||V|/2.
Christian Sohler
7
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Testing Expansion:
• Accept every graph that is an a-expander
• Reject every graph that is e-far from an a*-expander
• If not an a-expander and not e-far then we can accept or
reject
• Look at as few entries in the graph representation as
possible
Christian Sohler
8
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Related results:
Definition of bounded degree graph model; connectivity, k-connectivity, circle
freeness
[Goldreich, Ron; Algorithmica]
Conjecture: Expansion can be tested O(n polylog(n)) time
[Goldreich, Ron; ECCC, 2000]
Rapidly mixing property of Markov chains
[Batu, Fortnow, Rubinfeld, Smith, White; FOCS‘00]
Parallel / follow-up work:
An expansion tester for bounded degree graphs
[Kale, Seshadhri, ICALP’08]
Testing the Expansion of a Graph
[Nachmias, Shapira, ECCC’07]
Christian Sohler
9
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Difficulty:
• Expansion is a rather global property
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 1: A good expander
Christian Sohler
10
Testing Expansion in Bounded Degree Graphs
Introduction
University of Dortmund
Difficulty:
• Expansion is a rather global property
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 2: e-far from expander
Christian Sohler
11
Testing Expansion in Bounded Degree Graphs
The algorithm of Goldreich and Ron
University of Dortmund
How to distinguish these two cases?
• Perform a random walk for L= poly(log n, 1/e) steps
• Case 1: Distribution of end points is essentially uniform
• Case 2: Random walk will typically not cross cut
-> distribution differs significantly from uniform
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 1: A good expander
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 2: e-far from expander
Christian Sohler
12
Testing Expansion in Bounded Degree Graphs
The algorithm of Goldreich and Ron
University of Dortmund
How to distinguish these
Idea:two cases?
Count
the number
of collisions
• Perform a random walk for
L= poly(log
n, 1/e)
steps
among
end
of random
walks
• Case 1: Distribution of end
points
is points
essentially
uniform
• Case 2: Random walk will typically not cross cut
-> distribution differs significantly from uniform
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 1: A good expander
Expander
with n/2
vertices
Expander
with n/2
vertices
Case 2: e-far from expander
Christian Sohler
13
Testing Expansion in Bounded Degree Graphs
The algorithm of Goldreich and Ron
University of Dortmund
ExpansionTester(G,e,l,m,s)
1. repeat s times
2. choose vertex v uniformly at random from V
3. do m random walks of length L starting from v
4. count the number of collisions among endpoints
5. if #collisions> (1+e) E[#collisions in uniform distr.] then
reject
6. accept
Christian Sohler
14
Testing Expansion in Bounded Degree Graphs
Main result
University of Dortmund
ExpansionTester(G,e,l,m,s)
1. repeat s times
2. choose vertex v uniformly at random from V
3. do m random walks of length L starting from v
4. count the number of collisions among endpoints
5. if #collisions> (1+e) E[#collisions in uniform distr.] then
reject
6. accept
Theorem:[This work]
Algorithm ExpansionTester with s=Q(1/e), m=Q(n/poly(e)) and
L= poly(log n, d, 1/a, 1/e) accepts every a-expander with
probability at least 2/3 and rejects every graph, that is e-far
from every a*-expander with probability 2/3, where
a* = Q(a²/(d² log (n/e)).
Christian Sohler
15
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Overview of the proof:
• Algorithm ExpansionTester accepts every a-expander with
probability at least 2/3
Christian Sohler
16
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Overview of the proof:
• Algorithm ExpansionTester accepts every a-expander with
probability at least 2/3  (Chebyshev inequality)
Christian Sohler
17
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Overview of the proof:
• Algorithm ExpansionTester accepts every a-expander with
probability at least 2/3  (Chebyshev inequality)
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
Christian Sohler
18
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Overview of the proof:
• Algorithm ExpansionTester accepts every a-expander with
probability at least 2/3  (Chebyshev inequality)
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
• If G has a set U of dn vertices such that N(U) is small, then
ExpansionTester rejects
Christian Sohler
19
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Overview of the proof:
• Algorithm ExpansionTester accepts every a-expander with
probability at least 2/3  (Chebyshev inequality)
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
• If G has a set U of dn vertices such that N(U) is small, then
ExpansionTester rejects
 Random walk is unlikely to cross cut -> more collisions
Christian Sohler
20
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
Christian Sohler
21
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
Lemma:
If G is e-far from an a*-expander, then for every AV of size at
most en/4 we have that G[V-A] is not a (ca*)-expander
Christian Sohler
22
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
• If G is e-far from an a*-expander, then it contains a set U of
dn vertices such that N(U) is small
U
G
Lemma:
If G is e-far from an a*-expander, then for every AV of size at
most en/4 we have that G[V-A] is not a (ca*)-expander
Procedure to construct U:
• As long as U is too small apply lemma with A=U
• Since G[V-A] is not an expander, we have a set B of vertices that
is badly connected to the rest of G[V-A]
• Add B to U
Christian Sohler
23
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Lemma:
If G is e-far from an a*-expander, then for every AV of size at
most en/4 we have that G[V-A] is not a (ca*)-expander
Proof (by contradiction):
• Assume A as in lemma exists with G[V-A] is (ca*)-expander
• Construct from G an a*-expander
G
by changing at most edn
edges
• Contradiction: G is not
A
e-far from a*-expander
(ca*)-Expander
Christian Sohler
24
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
University of Dortmund
Lemma:
If G is e-far from an a*-expander, then for every AV of size at
most en/4 we have that G[V-A] is not a (ca*)-expander
Proof (by contradiction):
Construction of a*-expander:
1. Remove edges incident to A
2. Add (d-1)-regular
c‘-expander to A
3. Remove arbitrary matching M
of size |A|/2 from G[V-A]
4. Match endpoints of M with
points from A
G
A
(ca*)-Expander
Christian Sohler
25
University of Dortmund
Testing Expansion in Bounded Degree Graphs
Analysis of the algorithm
Lemma:
If G is e-far from an a*-expander, then for every AV of size at
most en/4 we have that G[V-A] is not a (ca*)-expander
Proof (by contradiction):
Construction of a*-expander:
1. Remove edges incident to A
2. Add (d-1)-regular
c‘-expander to A
3. Remove arbitrary matching M
of size |A|/2 from G[V-A]
4. Match endpoints of M with
points from A
Show that every set X
G
has large neighborhood
by case distinction
A
X
(ca*)-Expander
Christian Sohler
26
Testing Expansion in Bounded Degree Graphs
Main result
University of Dortmund
ExpansionTester(G,e,l,m,s)
1. repeat s times
2. choose vertex v uniformly at random from V
3. do m random walks of length L starting from v
4. count the number of collisions among endpoints
5. if #collisions> (1+e) E[#collisions in unif. Distr.] then reject
6. accept
Theorem:[This work]
Algorithm ExpansionTester with s=Q(1/e), m=Q(n/poly(e)) and
L= poly(log n, d, 1/a, 1/e) accepts every a-expander with
probability at least 2/3 and rejects every graph, that is e-far
from every a*-expander with probability 2/3, where
a* = poly(1/log n, 1/d, a, e).
Christian Sohler
27
University of Dortmund
Thank you!
Christian Sohler
28