Transcript Greedy Algorithm

On the Bisection of 4-regular
random graphs.
J.Díaz, N.Do, M.J.Serna, N.Wormald
Bisection
Given a graph with |V|=n even, a bisection
is a partition of V into two disjoints subsets
each with size n/2
Minimum Bisection
Find a bisection with minimum number of
crossing edges. The number of crossing
edges is the bisection width
bw=1
Maximum Bisection
Find a bisection with maximum number of
crossing edges.
Maxbis=5
Important problem in network communication
Both versions are NP-Hard, even for d-regular graphs
Min Bisection is non APX
Plenty of heuristics
Lower Bounds:
Fiedler (1974): The bw of any graph
Bollobas (1984): a.a. d-regular graphs have bw
Kostochka,Melnikov (1992): There are cubic graphs with bw
at least 0.101010101n.....
Lower Bounds:
Bezroukov et al. (2000):
The bw of a 3-regular Ramanujan graph is at least 0.042n
The bw of a 4-regular Ramanujan graph is at least 0.133n.....
Upper Bounds:
Kostochka-Melnikov (1992):
All d-reg. graphs have bisection width size
at most
Monien-Preis (2001):
Large 3-reg. graphs have bw of at most (0.166666+e)n
Large 4-reg. graphs have bw of at most (0.4+e)n
Our Goal
Give asymptotic estimates for the upper bound to the
bisection width of random 4-regular graph.
To do it design a randomize greedy algorithm, that at
each iteration colors differently a pair of vertices, and
analyze the expected bisection width obtained on an
input random 4-regular graph taken u.a.r.
Results:
Theorem 1: The bisection width of a
random 4-regular graph is a.a.s. smaller
than 0.333333333333n
Theorem 2: The size of the Max
bisection of a random 4-regular graph
is a.a.s. Smaller than 1.66666666667n
Also:
Theorem A: The bisection width of a
random 3-regular graph is a.a.s. smaller
than 0.174039n ( proceedings)
Theorem B: The bisection width of a
random 5-regular graph is a.a.s. smaller
than 0.5135...n
Classification of the vertices
Classify the non-colored vertices of G as:
Type (i,j): i neighbors red and j neighbors green
Ex:
Type (0,3):
Type (2,1):
Operations:
Majority: Choose uar vertices (i,j) and (j,i), i different j,
and color them as the majority of neighbors
Ex: (2,1) and (1,2):
Operations:
Random: Choose uar non-adjacent vertices (i,i) and (i,i) and
color one of them r and the other g
Ex: (1,1) and (1,1):
Greedy algorithm for Bisection (4-reg.)
0 - Select 2 vertices u.a.r. Color one r and the other g
1.- Repeat
if there are 2 vertices (2,0) and (0,2),
or if there are (2,1) and (1,2), then majority.
else if there are (1,0) and (0,1), then majority.
until no new vertex is colored.
F.- majority+random on the few remaining pairs
Example
Phase 0
Phase 0
01
10
10
11
10
01
01
Phase 1
10
10
10
02
01
11
20
01
01
Phase 1
10
10
01
10
10
01
01
11
10
01
01
Phase 1
11
01
20
20
11
11
10
01
01
01
Phase 1
21
20
20
12
12
12
11
02
Phase 1
21
20
12
12
11
02
Phase 1
20
22
21
03
Final Phase
bisection=8
Analysis of the performace
The DE method The differential equation method for
random processes (In:Lect. In Approx. And Randomization
73-155, PWN 1999.)
Define r.v. which indicates the evolution of the type
of vertices, compute the expected changes of the r.v.
after each iteration of the algorithm. Regard the r.v.
as continuous and write the ODE suggested by the
expected changes and show that whp, the solution
to this DE is concentrated around the value of the
variables.
Random generation of cubic
graphs
To generate a 4-regular G:
• Take n buckets, each with 4 points
• choose a random perfect matching:
pairing
(Bollobas: Random graphs, 1985)
Exposing a pair of points
Equations
Let Zrg = number of uncolored vertices
of type (r,g) .
At any time, the number of points not
involved in exposed pairs is:
W=4Z00+3Z01+3Z10+2Z02+2Z20+2Z11+
+Z21+Z12+Z03+Z30
We wish to compute E{ D(Zrg)} from t to t+1
Define drg as the average contribution
to D(Zrg) of exposing a pair of points
Due to coloring r one vertex v, one of the pairs (p,q), p in v,
is exposed:
d21=(2Z11 -Z21 )/W
v
In the same way compute all dij due to coloring R
Consider the corresponding symmetric equations for G
after the expected increments tdij due to a dual step R & G
td12=(2Z02+2Z11- 2Z12)/W
Assume in phase 1, (0,1)-(0,1) is processed
with probability f1; (2,0)-(0,2) is processed with
probability f2; and (2,1)-(1,2) is processed with
probability f3.
When processing (1,0)-(0,1) it produces in expectation
3 td02 pairs (2,0)-(0,2) and 3 td21 pairs (2,1)-(1,2).
Processing (2,0)-(0,2) produces in expectation 2td02
pairs (2,0)-(0,2) and 2dt02 pairs (2,1)-(1,2).
Processing (2,1)-(1,2) produces in expectation td02
Pairs (2,0)-(0,2) and dt21 pairs (2,1)-(1,2)
We get the system of equations
f1+f2+f3=1
f2=(3 f1+2 f2+ f3) td02
f3=(3 f1+2 f2+ f3) td01
Solve for f1,f2 and f3
DE for phase 1
Compute the expected increments of Zij at each iteration
in phase 1:
E[D(Zij)]= tdij (3f3+2f2+f1)-f1 d01-f2d02-f3d10
Express the increments as a set of DE with
E[D(Zij)]=Z’ij (x)
Let Y be a r.v. Keeping track of pairs (2,1)-(1,2) at each
Iteration of the algorithm. Each coloring of that pair will
contribute with 2 to the bisection.
Scaling down making Zij/n=zij, w=W/n, we get
The following ODE for phase 1,
z´00(x)= - D8 z00(x)/ w
z´01(x)=-f1 +D(4 z00(x) - 6z01(x))/ w
z´02(x)=-f2+D(3 z01(x) – 4 z02(x)) / w
z´11(x)=D(6z01(x)- 4z02(x))/ w
z´12(x)= -f3 D (2z02(x) + 2z11(x)- 2z12(x)) / w
y’(x) = 2f3
and initial conditions at x=t/n=0,
z00=1; z01=z02=z11=z12=y=0
Numerical Solution
Phase 1 finishes at iteration
x1=sup{x| f1=0} .
The upper bound on the bisection width
is given by sum of y in all iterations.
Solving numerically we get all the vertices are coloded
in phase 1 (zij=0) and bw< 1/3 + 10-5.5
To prove concentration, we need more.
Deprioritised
Pre 1 - repeat e n times
select 2 non-adjacent (0,0) vertices u.a.r.
Color one r and the other g
1.- while Z01,Z10 , Z20,Z02 , Z21 ,Z12 >0
with probability f1 MAJ on (1,0)-(0,1)
with probability f2 do MAJ on (2,0)-(0,2)
with probability f3 do MAJ on (2,1)-(1,2)
F.- as in priorized algorithm
Max Bisection: Operations
MIN: Choose uar vertices (i,j) and (j,i) and color them with
the missing color
The algorithm max greedy
Use the same algorithm as for Min Bisection, with
the symetrical operations: minority.
Then the monochromatic edges produced
by the min greedy result bichromatic by
max greedy, and viceversa.
As the total number of edges in a cubic graph is
2n, Theorem 2 follows.
Greedy algorithm for Bisection (5-reg)
0 - Select 2 vertices u.a.r. Color one r and the other g
1.- Repeat
if there are 2 vertices (2,0) and (0,2),
or if there are (2,1) and (1,2), then majority.
else if there are (1,0) and (0,1), then majority.
until no new vertex is colored.
2.- Repeat
if there are (2,0) and (0,2)
or there are (3,1) and (1,3) then majority
else if there are (2,1) and (1,2) then majority
until no new vertex is colored
3.- Repeat
if there are 2 vertices (1,2) and (2,1), then majority.
else if there are (1,1) and (1,1), then random.
until no new vertex is colored.
F.- majority+random on the few remaining pairs