1 of 58

On Efficient Computation of �DiRe Committees���Kunal Relia�kunal.relia91@gmail.com, krelia@nyu.edu�����July 11, 2023

2 of 58

(Contextually) Equivalent to: �On Efficient Computation of Minimum Vertex Cover���Kunal Relia�kunal.relia91@gmail.com, krelia@nyu.edu�����July 11, 2023

3 of 58

An Algorithm for an NP-complete problem

  • Amalgamation of:

​

    • Maximum Matching

​

    • Breadth-First Search

​

    • Maximal Matching

​

    • Local Minimization

​

  • Algorithm is specifically for unweighted simple connected graphs

4 of 58

EXAMPLE 1

(simultaneously read notes)

5 of 58

1

5

4

2

3

6

7

8

0

6 of 58

1

5

4

2

3

6

7

8

0

Maximum Matching

​

​

7 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

8 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

9 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0

1

10 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1

11 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

12 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

13 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

14 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

15 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2

7

16 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

17 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

18 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3

5

19 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

20 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

21 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

22 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4

6

23 of 58

1

5

4

2

3

6

7

8

0

BFS

​

​

Level

Vertices

A

0

B

1

C

2, 3

D

4, 5, 7, 8

E

6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

24 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

25 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

26 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

27 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

28 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

29 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

30 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

31 of 58

Local Minimization

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

32 of 58

Smallest Vertex Cover = {1, 2, 3, 6}

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

33 of 58

Minimum Vertex Cover = {1, 2, 3, 6}

Node 1

Node 2

0 – {1}

1 – {0, 2, 3}

2 – {4, 7}

7 – {2}

3 – {5, 8}

5 – {3, 6}

4 – {6}

6 – {4}

34 of 58

1

5

4

2

3

6

7

8

0

Minimum Vertex Cover = {1, 2, 3, 6}

35 of 58

Proof Sketch

36 of 58

Proof Sketch

If a given instance of Vertex Cover is a ``Yes'' instance, then the Algorithm returns ``Yes’’.

  • This case is relatively trivial.

If the Algorithm returns ``Yes'', then the given instance of Vertex Cover is a ``Yes'' instance.

​

  1. Maximum matching assigns "weight" to unweighted edges.

​

  • BFS (once by seeding on each vertex) assigns "direction" to undirected edges. 

​

  • (for each BFS,) Maximal matching ensures we get a vertex cover.

​

  • (for each BFS,) Local minimization happens, with caution, in the reverse "direction" as compared to 2.

​

  • 1 + 2 + 4 ensures we get a global minimum.

​

  • 5 + 3 ensures we get a minimum vertex cover.

​

37 of 58

EXAMPLE 2

(notes deliberately absent –

refer to notes of Example 1 to

traverse through the example)

38 of 58

0

6

5

4

2

1

3

39 of 58

0

6

5

4

2

1

3

Maximum Matching

​

​

40 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

41 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

42 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

Node 1

Node 2

0

1

43 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1

44 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

Acknowledgement: Creators and maintainers at VisuAlgo as their website helped me visualize vertex cover in the desired manner - http://visualgo.net/

45 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

46 of 58

0

6

5

4

2

1

3

BFS

​

​

Level

Vertices

A

0

B

1, 2, 3

C

4, 5, 6

Maximal Matching

​

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

47 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

48 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

49 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

50 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

51 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

52 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

53 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

54 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

55 of 58

Local Minimization

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

56 of 58

Minimum Vertex Cover: {1, 2, 3}

​

​

​

Node 1

Node 2

0 – {1, 2, 3}

1 – {0, 4}

2 – {5}

5 – {2}

3 – {6}

6 – {3}

57 of 58

Minimum Vertex Cover: {1, 2, 3}

​

​

​

0

6

5

4

2

1

3

58 of 58

Thank You!

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