1 of 26

EXAMPLE 3

(demonstrates the rationale

behind naming of maximal

matching and local minimization)

2 of 26

1

5

4

2

3

6

7

8

0

3 of 26

1

5

4

2

3

6

7

8

0

Maximum Matching

​

​

4 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

5 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

6 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

Maximal Matching

​

​

​

​

Node 1

Node 2

0

1

7 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

Node 1

Node 2

0 – {1}

1

8 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

9 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

10 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

11 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

12 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3

5

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

13 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

14 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

15 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2

4

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

16 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

17 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

18 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

Level

Vertices

A

0

B

1

C

2, 3, 4, 5

D

6, 7, 8

19 of 26

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

20 of 26

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

21 of 26

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

22 of 26

Smallest Vertex Cover = {1, 2, 3, 4, 5}

Node 1

Node 2

0 – {1}

1 – {0, 2, 3, 4, 5}

3 – {5, 8}

5 – {3, 6}

2 – {4, 7}

4 – {2, 6}

23 of 26

1

5

4

2

3

6

7

8

0

Maximum Matching

​

​

24 of 26

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

3

B

1, 5, 8

C

0, 2, 4, 6

D

7

25 of 26

1

5

4

2

3

6

7

8

0

26 of 26

Thank You!

Author, while at NYU, was generously supported in part by Julia Stoyanovich’s NSF grants.