********* EXAMPLE 1 ********* n = 10 m = 13 +++ Path lengths: 2 1 3 3 1 1 2 3 1 2 +++ Edges: ( 5, 9) ( 7, 8) ( 0, 7) ( 2, 6) ( 3, 5) ( 2, 4) ( 1, 3) ( 1, 2) ( 0, 1) ( 0, 4) ( 6, 7) ( 4, 7) ( 6, 8) +++ Input graph Number of vertices: 10 Number of edges : 13 0 (2) -> 4, 1, 7 1 (1) -> 0, 2, 3 2 (3) -> 1, 4, 6 3 (3) -> 1, 5 4 (1) -> 7, 0, 2 5 (1) -> 3, 9 6 (2) -> 8, 7, 2 7 (3) -> 4, 6, 0, 8 8 (1) -> 6, 7 9 (2) -> 5 +++ Reachability graph Number of vertices: 10 Number of edges : 37 0 (2) -> 2, 3, 4, 6, 7, 8 1 (1) -> 0, 2, 3 2 (3) -> 0, 1, 4, 5, 6, 7, 8 3 (3) -> 4, 6, 7 4 (1) -> 0, 2, 7 5 (1) -> 3, 9 6 (2) -> 0, 1, 4, 7, 8 7 (3) -> 1, 2, 3, 4, 6 8 (1) -> 6, 7 9 (2) -> 3 +++ Simultaneous reachability graph Number of vertices: 100 Number of edges : 1369 0 (4) -> 88, 87, 86, 84, 83, 82, 78, 77, 76, 74, 73, 72, 68, 67, 66, 64, 63, 62, 48, 47, 46, 44, 43, 42, 38, 37, 36, 34, 33, 32, 28, 27, 26, 24, 23, 22 1 (3) -> 83, 82, 80, 73, 72, 70, 63, 62, 60, 43, 42, 40, 33, 32, 30, 23, 22, 20 2 (5) -> 88, 87, 86, 85, 84, 81, 80, 78, 77, 76, 75, 74, 71, 70, 68, 67, 66, 65, 64, 61, 60, 48, 47, 46, 45, 44, 41, 40, 38, 37, 36, 35, 34, 31, 30, 28, 27, 26, 25, 24, 21, 20 3 (5) -> 87, 86, 84, 77, 76, 74, 67, 66, 64, 47, 46, 44, 37, 36, 34, 27, 26, 24 4 (3) -> 87, 82, 80, 77, 72, 70, 67, 62, 60, 47, 42, 40, 37, 32, 30, 27, 22, 20 5 (3) -> 89, 83, 79, 73, 69, 63, 49, 43, 39, 33, 29, 23 6 (4) -> 88, 87, 84, 81, 80, 78, 77, 74, 71, 70, 68, 67, 64, 61, 60, 48, 47, 44, 41, 40, 38, 37, 34, 31, 30, 28, 27, 24, 21, 20 7 (5) -> 86, 84, 83, 82, 81, 76, 74, 73, 72, 71, 66, 64, 63, 62, 61, 46, 44, 43, 42, 41, 36, 34, 33, 32, 31, 26, 24, 23, 22, 21 8 (3) -> 87, 86, 77, 76, 67, 66, 47, 46, 37, 36, 27, 26 9 (4) -> 83, 73, 63, 43, 33, 23 10 (3) -> 38, 37, 36, 34, 33, 32, 28, 27, 26, 24, 23, 22, 8, 7, 6, 4, 3, 2 11 (2) -> 33, 32, 30, 23, 22, 20, 3, 2, 0 12 (4) -> 38, 37, 36, 35, 34, 31, 30, 28, 27, 26, 25, 24, 21, 20, 8, 7, 6, 5, 4, 1, 0 13 (4) -> 37, 36, 34, 27, 26, 24, 7, 6, 4 14 (2) -> 37, 32, 30, 27, 22, 20, 7, 2, 0 15 (2) -> 39, 33, 29, 23, 9, 3 16 (3) -> 38, 37, 34, 31, 30, 28, 27, 24, 21, 20, 8, 7, 4, 1, 0 17 (4) -> 36, 34, 33, 32, 31, 26, 24, 23, 22, 21, 6, 4, 3, 2, 1 18 (2) -> 37, 36, 27, 26, 7, 6 19 (3) -> 33, 23, 3 20 (5) -> 88, 87, 86, 84, 83, 82, 78, 77, 76, 74, 73, 72, 68, 67, 66, 64, 63, 62, 58, 57, 56, 54, 53, 52, 48, 47, 46, 44, 43, 42, 18, 17, 16, 14, 13, 12, 8, 7, 6, 4, 3, 2 21 (4) -> 83, 82, 80, 73, 72, 70, 63, 62, 60, 53, 52, 50, 43, 42, 40, 13, 12, 10, 3, 2, 0 22 (6) -> 88, 87, 86, 85, 84, 81, 80, 78, 77, 76, 75, 74, 71, 70, 68, 67, 66, 65, 64, 61, 60, 58, 57, 56, 55, 54, 51, 50, 48, 47, 46, 45, 44, 41, 40, 18, 17, 16, 15, 14, 11, 10, 8, 7, 6, 5, 4, 1, 0 23 (6) -> 87, 86, 84, 77, 76, 74, 67, 66, 64, 57, 56, 54, 47, 46, 44, 17, 16, 14, 7, 6, 4 24 (4) -> 87, 82, 80, 77, 72, 70, 67, 62, 60, 57, 52, 50, 47, 42, 40, 17, 12, 10, 7, 2, 0 25 (4) -> 89, 83, 79, 73, 69, 63, 59, 53, 49, 43, 19, 13, 9, 3 26 (5) -> 88, 87, 84, 81, 80, 78, 77, 74, 71, 70, 68, 67, 64, 61, 60, 58, 57, 54, 51, 50, 48, 47, 44, 41, 40, 18, 17, 14, 11, 10, 8, 7, 4, 1, 0 27 (6) -> 86, 84, 83, 82, 81, 76, 74, 73, 72, 71, 66, 64, 63, 62, 61, 56, 54, 53, 52, 51, 46, 44, 43, 42, 41, 16, 14, 13, 12, 11, 6, 4, 3, 2, 1 28 (4) -> 87, 86, 77, 76, 67, 66, 57, 56, 47, 46, 17, 16, 7, 6 29 (5) -> 83, 73, 63, 53, 43, 13, 3 30 (5) -> 78, 77, 76, 74, 73, 72, 68, 67, 66, 64, 63, 62, 48, 47, 46, 44, 43, 42 31 (4) -> 73, 72, 70, 63, 62, 60, 43, 42, 40 32 (6) -> 78, 77, 76, 75, 74, 71, 70, 68, 67, 66, 65, 64, 61, 60, 48, 47, 46, 45, 44, 41, 40 33 (6) -> 77, 76, 74, 67, 66, 64, 47, 46, 44 34 (4) -> 77, 72, 70, 67, 62, 60, 47, 42, 40 35 (4) -> 79, 73, 69, 63, 49, 43 36 (5) -> 78, 77, 74, 71, 70, 68, 67, 64, 61, 60, 48, 47, 44, 41, 40 37 (6) -> 76, 74, 73, 72, 71, 66, 64, 63, 62, 61, 46, 44, 43, 42, 41 38 (4) -> 77, 76, 67, 66, 47, 46 39 (5) -> 73, 63, 43 40 (3) -> 78, 77, 76, 74, 73, 72, 28, 27, 26, 24, 23, 22, 8, 7, 6, 4, 3, 2 41 (2) -> 73, 72, 70, 23, 22, 20, 3, 2, 0 42 (4) -> 78, 77, 76, 75, 74, 71, 70, 28, 27, 26, 25, 24, 21, 20, 8, 7, 6, 5, 4, 1, 0 43 (4) -> 77, 76, 74, 27, 26, 24, 7, 6, 4 44 (2) -> 77, 72, 70, 27, 22, 20, 7, 2, 0 45 (2) -> 79, 73, 29, 23, 9, 3 46 (3) -> 78, 77, 74, 71, 70, 28, 27, 24, 21, 20, 8, 7, 4, 1, 0 47 (4) -> 76, 74, 73, 72, 71, 26, 24, 23, 22, 21, 6, 4, 3, 2, 1 48 (2) -> 77, 76, 27, 26, 7, 6 49 (3) -> 73, 23, 3 50 (3) -> 98, 97, 96, 94, 93, 92, 38, 37, 36, 34, 33, 32 51 (2) -> 93, 92, 90, 33, 32, 30 52 (4) -> 98, 97, 96, 95, 94, 91, 90, 38, 37, 36, 35, 34, 31, 30 53 (4) -> 97, 96, 94, 37, 36, 34 54 (2) -> 97, 92, 90, 37, 32, 30 55 (2) -> 99, 93, 39, 33 56 (3) -> 98, 97, 94, 91, 90, 38, 37, 34, 31, 30 57 (4) -> 96, 94, 93, 92, 91, 36, 34, 33, 32, 31 58 (2) -> 97, 96, 37, 36 59 (3) -> 93, 33 60 (4) -> 88, 87, 86, 84, 83, 82, 78, 77, 76, 74, 73, 72, 48, 47, 46, 44, 43, 42, 18, 17, 16, 14, 13, 12, 8, 7, 6, 4, 3, 2 61 (3) -> 83, 82, 80, 73, 72, 70, 43, 42, 40, 13, 12, 10, 3, 2, 0 62 (5) -> 88, 87, 86, 85, 84, 81, 80, 78, 77, 76, 75, 74, 71, 70, 48, 47, 46, 45, 44, 41, 40, 18, 17, 16, 15, 14, 11, 10, 8, 7, 6, 5, 4, 1, 0 63 (5) -> 87, 86, 84, 77, 76, 74, 47, 46, 44, 17, 16, 14, 7, 6, 4 64 (3) -> 87, 82, 80, 77, 72, 70, 47, 42, 40, 17, 12, 10, 7, 2, 0 65 (3) -> 89, 83, 79, 73, 49, 43, 19, 13, 9, 3 66 (4) -> 88, 87, 84, 81, 80, 78, 77, 74, 71, 70, 48, 47, 44, 41, 40, 18, 17, 14, 11, 10, 8, 7, 4, 1, 0 67 (5) -> 86, 84, 83, 82, 81, 76, 74, 73, 72, 71, 46, 44, 43, 42, 41, 16, 14, 13, 12, 11, 6, 4, 3, 2, 1 68 (3) -> 87, 86, 77, 76, 47, 46, 17, 16, 7, 6 69 (4) -> 83, 73, 43, 13, 3 70 (5) -> 68, 67, 66, 64, 63, 62, 48, 47, 46, 44, 43, 42, 38, 37, 36, 34, 33, 32, 28, 27, 26, 24, 23, 22, 18, 17, 16, 14, 13, 12 71 (4) -> 63, 62, 60, 43, 42, 40, 33, 32, 30, 23, 22, 20, 13, 12, 10 72 (6) -> 68, 67, 66, 65, 64, 61, 60, 48, 47, 46, 45, 44, 41, 40, 38, 37, 36, 35, 34, 31, 30, 28, 27, 26, 25, 24, 21, 20, 18, 17, 16, 15, 14, 11, 10 73 (6) -> 67, 66, 64, 47, 46, 44, 37, 36, 34, 27, 26, 24, 17, 16, 14 74 (4) -> 67, 62, 60, 47, 42, 40, 37, 32, 30, 27, 22, 20, 17, 12, 10 75 (4) -> 69, 63, 49, 43, 39, 33, 29, 23, 19, 13 76 (5) -> 68, 67, 64, 61, 60, 48, 47, 44, 41, 40, 38, 37, 34, 31, 30, 28, 27, 24, 21, 20, 18, 17, 14, 11, 10 77 (6) -> 66, 64, 63, 62, 61, 46, 44, 43, 42, 41, 36, 34, 33, 32, 31, 26, 24, 23, 22, 21, 16, 14, 13, 12, 11 78 (4) -> 67, 66, 47, 46, 37, 36, 27, 26, 17, 16 79 (5) -> 63, 43, 33, 23, 13 80 (3) -> 78, 77, 76, 74, 73, 72, 68, 67, 66, 64, 63, 62 81 (2) -> 73, 72, 70, 63, 62, 60 82 (4) -> 78, 77, 76, 75, 74, 71, 70, 68, 67, 66, 65, 64, 61, 60 83 (4) -> 77, 76, 74, 67, 66, 64 84 (2) -> 77, 72, 70, 67, 62, 60 85 (2) -> 79, 73, 69, 63 86 (3) -> 78, 77, 74, 71, 70, 68, 67, 64, 61, 60 87 (4) -> 76, 74, 73, 72, 71, 66, 64, 63, 62, 61 88 (2) -> 77, 76, 67, 66 89 (3) -> 73, 63 90 (4) -> 38, 37, 36, 34, 33, 32 91 (3) -> 33, 32, 30 92 (5) -> 38, 37, 36, 35, 34, 31, 30 93 (5) -> 37, 36, 34 94 (3) -> 37, 32, 30 95 (3) -> 39, 33 96 (4) -> 38, 37, 34, 31, 30 97 (5) -> 36, 34, 33, 32, 31 98 (3) -> 37, 36 99 (4) -> 33 s = 5 t = 9 +++ Minimum number of steps --- Allowing robots to share a node Steps: (5,9) (3,3) (7,7) (2,4) (5,2) (9,5) Number of steps = 5 Total effort = 23 --- Disallowing robots to share a node Steps: (5,9) (9,3) (3,7) (7,6) (2,7) (5,2) (9,5) Number of steps = 6 Total effort = 29 +++ Minimum total combined effort --- Allowing robots to share a node Steps: (5,9) (3,3) (4,4) (2,0) (5,2) (9,5) Number of steps = 5 Total effort = 20 --- Disallowing robots to share a node Steps: (5,9) (9,3) (3,4) (4,0) (2,4) (5,2) (9,5) Number of steps = 6 Total effort = 23 ********* EXAMPLE 2 ********* n = 10 m = 12 +++ Path lengths: 1 3 2 1 1 1 1 1 1 3 +++ Edges: ( 2, 9) ( 6, 8) ( 3, 7) ( 4, 6) ( 2, 5) ( 0, 4) ( 2, 3) ( 1, 2) ( 0, 1) ( 0, 5) ( 0, 6) ( 0, 9) +++ Input graph Number of vertices: 10 Number of edges : 12 0 (1) -> 9, 6, 5, 1, 4 1 (3) -> 0, 2 2 (2) -> 1, 3, 5, 9 3 (1) -> 2, 7 4 (1) -> 0, 6 5 (1) -> 0, 2 6 (1) -> 0, 4, 8 7 (1) -> 3 8 (1) -> 6 9 (3) -> 0, 2 +++ Reachability graph Number of vertices: 10 Number of edges : 30 0 (1) -> 1, 4, 5, 6, 9 1 (3) -> 0, 2, 4, 6, 7, 8 2 (2) -> 0, 7 3 (1) -> 2, 7 4 (1) -> 0, 6 5 (1) -> 0, 2 6 (1) -> 0, 4, 8 7 (1) -> 3 8 (1) -> 6 9 (3) -> 0, 2, 4, 6, 7, 8 +++ Simultaneous reachability graph Number of vertices: 100 Number of edges : 900 0 (2) -> 99, 96, 95, 94, 91, 69, 66, 65, 64, 61, 59, 56, 55, 54, 51, 49, 46, 45, 44, 41, 19, 16, 15, 14, 11 1 (4) -> 98, 97, 96, 94, 92, 90, 68, 67, 66, 64, 62, 60, 58, 57, 56, 54, 52, 50, 48, 47, 46, 44, 42, 40, 18, 17, 16, 14, 12, 10 2 (3) -> 97, 90, 67, 60, 57, 50, 47, 40, 17, 10 3 (2) -> 97, 92, 67, 62, 57, 52, 47, 42, 17, 12 4 (2) -> 96, 90, 66, 60, 56, 50, 46, 40, 16, 10 5 (2) -> 92, 90, 62, 60, 52, 50, 42, 40, 12, 10 6 (2) -> 98, 94, 90, 68, 64, 60, 58, 54, 50, 48, 44, 40, 18, 14, 10 7 (2) -> 93, 63, 53, 43, 13 8 (2) -> 96, 66, 56, 46, 16 9 (4) -> 98, 97, 96, 94, 92, 90, 68, 67, 66, 64, 62, 60, 58, 57, 56, 54, 52, 50, 48, 47, 46, 44, 42, 40, 18, 17, 16, 14, 12, 10 10 (4) -> 89, 86, 85, 84, 81, 79, 76, 75, 74, 71, 69, 66, 65, 64, 61, 49, 46, 45, 44, 41, 29, 26, 25, 24, 21, 9, 6, 5, 4, 1 11 (6) -> 88, 87, 86, 84, 82, 80, 78, 77, 76, 74, 72, 70, 68, 67, 66, 64, 62, 60, 48, 47, 46, 44, 42, 40, 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 12 (5) -> 87, 80, 77, 70, 67, 60, 47, 40, 27, 20, 7, 0 13 (4) -> 87, 82, 77, 72, 67, 62, 47, 42, 27, 22, 7, 2 14 (4) -> 86, 80, 76, 70, 66, 60, 46, 40, 26, 20, 6, 0 15 (4) -> 82, 80, 72, 70, 62, 60, 42, 40, 22, 20, 2, 0 16 (4) -> 88, 84, 80, 78, 74, 70, 68, 64, 60, 48, 44, 40, 28, 24, 20, 8, 4, 0 17 (4) -> 83, 73, 63, 43, 23, 3 18 (4) -> 86, 76, 66, 46, 26, 6 19 (6) -> 88, 87, 86, 84, 82, 80, 78, 77, 76, 74, 72, 70, 68, 67, 66, 64, 62, 60, 48, 47, 46, 44, 42, 40, 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 20 (3) -> 79, 76, 75, 74, 71, 9, 6, 5, 4, 1 21 (5) -> 78, 77, 76, 74, 72, 70, 8, 7, 6, 4, 2, 0 22 (4) -> 77, 70, 7, 0 23 (3) -> 77, 72, 7, 2 24 (3) -> 76, 70, 6, 0 25 (3) -> 72, 70, 2, 0 26 (3) -> 78, 74, 70, 8, 4, 0 27 (3) -> 73, 3 28 (3) -> 76, 6 29 (5) -> 78, 77, 76, 74, 72, 70, 8, 7, 6, 4, 2, 0 30 (2) -> 79, 76, 75, 74, 71, 29, 26, 25, 24, 21 31 (4) -> 78, 77, 76, 74, 72, 70, 28, 27, 26, 24, 22, 20 32 (3) -> 77, 70, 27, 20 33 (2) -> 77, 72, 27, 22 34 (2) -> 76, 70, 26, 20 35 (2) -> 72, 70, 22, 20 36 (2) -> 78, 74, 70, 28, 24, 20 37 (2) -> 73, 23 38 (2) -> 76, 26 39 (4) -> 78, 77, 76, 74, 72, 70, 28, 27, 26, 24, 22, 20 40 (2) -> 69, 66, 65, 64, 61, 9, 6, 5, 4, 1 41 (4) -> 68, 67, 66, 64, 62, 60, 8, 7, 6, 4, 2, 0 42 (3) -> 67, 60, 7, 0 43 (2) -> 67, 62, 7, 2 44 (2) -> 66, 60, 6, 0 45 (2) -> 62, 60, 2, 0 46 (2) -> 68, 64, 60, 8, 4, 0 47 (2) -> 63, 3 48 (2) -> 66, 6 49 (4) -> 68, 67, 66, 64, 62, 60, 8, 7, 6, 4, 2, 0 50 (2) -> 29, 26, 25, 24, 21, 9, 6, 5, 4, 1 51 (4) -> 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 52 (3) -> 27, 20, 7, 0 53 (2) -> 27, 22, 7, 2 54 (2) -> 26, 20, 6, 0 55 (2) -> 22, 20, 2, 0 56 (2) -> 28, 24, 20, 8, 4, 0 57 (2) -> 23, 3 58 (2) -> 26, 6 59 (4) -> 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 60 (2) -> 89, 86, 85, 84, 81, 49, 46, 45, 44, 41, 9, 6, 5, 4, 1 61 (4) -> 88, 87, 86, 84, 82, 80, 48, 47, 46, 44, 42, 40, 8, 7, 6, 4, 2, 0 62 (3) -> 87, 80, 47, 40, 7, 0 63 (2) -> 87, 82, 47, 42, 7, 2 64 (2) -> 86, 80, 46, 40, 6, 0 65 (2) -> 82, 80, 42, 40, 2, 0 66 (2) -> 88, 84, 80, 48, 44, 40, 8, 4, 0 67 (2) -> 83, 43, 3 68 (2) -> 86, 46, 6 69 (4) -> 88, 87, 86, 84, 82, 80, 48, 47, 46, 44, 42, 40, 8, 7, 6, 4, 2, 0 70 (2) -> 39, 36, 35, 34, 31 71 (4) -> 38, 37, 36, 34, 32, 30 72 (3) -> 37, 30 73 (2) -> 37, 32 74 (2) -> 36, 30 75 (2) -> 32, 30 76 (2) -> 38, 34, 30 77 (2) -> 33 78 (2) -> 36 79 (4) -> 38, 37, 36, 34, 32, 30 80 (2) -> 69, 66, 65, 64, 61 81 (4) -> 68, 67, 66, 64, 62, 60 82 (3) -> 67, 60 83 (2) -> 67, 62 84 (2) -> 66, 60 85 (2) -> 62, 60 86 (2) -> 68, 64, 60 87 (2) -> 63 88 (2) -> 66 89 (4) -> 68, 67, 66, 64, 62, 60 90 (4) -> 89, 86, 85, 84, 81, 79, 76, 75, 74, 71, 69, 66, 65, 64, 61, 49, 46, 45, 44, 41, 29, 26, 25, 24, 21, 9, 6, 5, 4, 1 91 (6) -> 88, 87, 86, 84, 82, 80, 78, 77, 76, 74, 72, 70, 68, 67, 66, 64, 62, 60, 48, 47, 46, 44, 42, 40, 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 92 (5) -> 87, 80, 77, 70, 67, 60, 47, 40, 27, 20, 7, 0 93 (4) -> 87, 82, 77, 72, 67, 62, 47, 42, 27, 22, 7, 2 94 (4) -> 86, 80, 76, 70, 66, 60, 46, 40, 26, 20, 6, 0 95 (4) -> 82, 80, 72, 70, 62, 60, 42, 40, 22, 20, 2, 0 96 (4) -> 88, 84, 80, 78, 74, 70, 68, 64, 60, 48, 44, 40, 28, 24, 20, 8, 4, 0 97 (4) -> 83, 73, 63, 43, 23, 3 98 (4) -> 86, 76, 66, 46, 26, 6 99 (6) -> 88, 87, 86, 84, 82, 80, 78, 77, 76, 74, 72, 70, 68, 67, 66, 64, 62, 60, 48, 47, 46, 44, 42, 40, 28, 27, 26, 24, 22, 20, 8, 7, 6, 4, 2, 0 s = 3 t = 8 +++ Minimum number of steps --- Allowing robots to share a node Steps: (3,8) (2,6) (0,0) (9,9) (6,7) (8,3) Number of steps = 5 Total effort = 15 --- Disallowing robots to share a node Steps: (3,8) (7,6) (3,4) (2,0) (0,9) (9,7) (8,3) Number of steps = 6 Total effort = 17 +++ Minimum total combined effort --- Allowing robots to share a node Steps: (3,8) (2,6) (0,0) (4,9) (6,7) (8,3) Number of steps = 5 Total effort = 13 --- Disallowing robots to share a node Steps: (3,8) (7,6) (3,0) (2,5) (0,2) (6,7) (8,3) Number of steps = 6 Total effort = 14 ********* EXAMPLE 3 ********* n = 10 m = 10 +++ Path lengths: 1 3 3 2 2 1 2 3 2 1 +++ Edges: ( 0, 9) ( 7, 8) ( 5, 7) ( 2, 6) ( 4, 5) ( 3, 4) ( 2, 3) ( 1, 2) ( 0, 1) ( 4, 8) +++ Input graph Number of vertices: 10 Number of edges : 10 0 (1) -> 1, 9 1 (3) -> 0, 2 2 (3) -> 1, 3, 6 3 (2) -> 2, 4 4 (2) -> 8, 3, 5 5 (1) -> 4, 7 6 (2) -> 2 7 (3) -> 5, 8 8 (2) -> 4, 7 9 (1) -> 0 +++ Reachability graph Number of vertices: 10 Number of edges : 22 0 (1) -> 1, 9 1 (3) -> 4 2 (3) -> 5, 8, 9 3 (2) -> 1, 5, 6, 8 4 (2) -> 2, 7 5 (1) -> 4, 7 6 (2) -> 1, 3 7 (3) -> 3, 5, 8 8 (2) -> 3, 5 9 (1) -> 0 +++ Simultaneous reachability graph Number of vertices: 100 Number of edges : 484 0 (2) -> 99, 91, 19, 11 1 (4) -> 94, 14 2 (4) -> 99, 98, 95, 19, 18, 15 3 (3) -> 98, 96, 95, 91, 18, 16, 15, 11 4 (3) -> 97, 92, 17, 12 5 (2) -> 97, 94, 17, 14 6 (3) -> 93, 91, 13, 11 7 (4) -> 98, 95, 93, 18, 15, 13 8 (3) -> 95, 93, 15, 13 9 (2) -> 90, 10 10 (4) -> 49, 41 11 (6) -> 44 12 (6) -> 49, 48, 45 13 (5) -> 48, 46, 45, 41 14 (5) -> 47, 42 15 (4) -> 47, 44 16 (5) -> 43, 41 17 (6) -> 48, 45, 43 18 (5) -> 45, 43 19 (4) -> 40 20 (4) -> 99, 91, 89, 81, 59, 51 21 (6) -> 94, 84, 54 22 (6) -> 99, 98, 95, 89, 88, 85, 59, 58, 55 23 (5) -> 98, 96, 95, 91, 88, 86, 85, 81, 58, 56, 55, 51 24 (5) -> 97, 92, 87, 82, 57, 52 25 (4) -> 97, 94, 87, 84, 57, 54 26 (5) -> 93, 91, 83, 81, 53, 51 27 (6) -> 98, 95, 93, 88, 85, 83, 58, 55, 53 28 (5) -> 95, 93, 85, 83, 55, 53 29 (4) -> 90, 80, 50 30 (3) -> 89, 81, 69, 61, 59, 51, 19, 11 31 (5) -> 84, 64, 54, 14 32 (5) -> 89, 88, 85, 69, 68, 65, 59, 58, 55, 19, 18, 15 33 (4) -> 88, 86, 85, 81, 68, 66, 65, 61, 58, 56, 55, 51, 18, 16, 15, 11 34 (4) -> 87, 82, 67, 62, 57, 52, 17, 12 35 (3) -> 87, 84, 67, 64, 57, 54, 17, 14 36 (4) -> 83, 81, 63, 61, 53, 51, 13, 11 37 (5) -> 88, 85, 83, 68, 65, 63, 58, 55, 53, 18, 15, 13 38 (4) -> 85, 83, 65, 63, 55, 53, 15, 13 39 (3) -> 80, 60, 50, 10 40 (3) -> 79, 71, 29, 21 41 (5) -> 74, 24 42 (5) -> 79, 78, 75, 29, 28, 25 43 (4) -> 78, 76, 75, 71, 28, 26, 25, 21 44 (4) -> 77, 72, 27, 22 45 (3) -> 77, 74, 27, 24 46 (4) -> 73, 71, 23, 21 47 (5) -> 78, 75, 73, 28, 25, 23 48 (4) -> 75, 73, 25, 23 49 (3) -> 70, 20 50 (2) -> 79, 71, 49, 41 51 (4) -> 74, 44 52 (4) -> 79, 78, 75, 49, 48, 45 53 (3) -> 78, 76, 75, 71, 48, 46, 45, 41 54 (3) -> 77, 72, 47, 42 55 (2) -> 77, 74, 47, 44 56 (3) -> 73, 71, 43, 41 57 (4) -> 78, 75, 73, 48, 45, 43 58 (3) -> 75, 73, 45, 43 59 (2) -> 70, 40 60 (3) -> 39, 31, 19, 11 61 (5) -> 34, 14 62 (5) -> 39, 38, 35, 19, 18, 15 63 (4) -> 38, 36, 35, 31, 18, 16, 15, 11 64 (4) -> 37, 32, 17, 12 65 (3) -> 37, 34, 17, 14 66 (4) -> 33, 31, 13, 11 67 (5) -> 38, 35, 33, 18, 15, 13 68 (4) -> 35, 33, 15, 13 69 (3) -> 30, 10 70 (4) -> 89, 81, 59, 51, 39, 31 71 (6) -> 84, 54, 34 72 (6) -> 89, 88, 85, 59, 58, 55, 39, 38, 35 73 (5) -> 88, 86, 85, 81, 58, 56, 55, 51, 38, 36, 35, 31 74 (5) -> 87, 82, 57, 52, 37, 32 75 (4) -> 87, 84, 57, 54, 37, 34 76 (5) -> 83, 81, 53, 51, 33, 31 77 (6) -> 88, 85, 83, 58, 55, 53, 38, 35, 33 78 (5) -> 85, 83, 55, 53, 35, 33 79 (4) -> 80, 50, 30 80 (3) -> 59, 51, 39, 31 81 (5) -> 54, 34 82 (5) -> 59, 58, 55, 39, 38, 35 83 (4) -> 58, 56, 55, 51, 38, 36, 35, 31 84 (4) -> 57, 52, 37, 32 85 (3) -> 57, 54, 37, 34 86 (4) -> 53, 51, 33, 31 87 (5) -> 58, 55, 53, 38, 35, 33 88 (4) -> 55, 53, 35, 33 89 (3) -> 50, 30 90 (2) -> 9, 1 91 (4) -> 4 92 (4) -> 9, 8, 5 93 (3) -> 8, 6, 5, 1 94 (3) -> 7, 2 95 (2) -> 7, 4 96 (3) -> 3, 1 97 (4) -> 8, 5, 3 98 (3) -> 5, 3 99 (2) -> 0 s = 0 t = 1 +++ Minimum number of steps --- Allowing robots to share a node Steps: (0,1) (1,4) (4,2) (7,9) (8,0) (3,9) (1,0) Number of steps = 6 Total effort = 24 --- Disallowing robots to share a node Steps: (0,1) (1,4) (4,2) (7,9) (8,0) (3,9) (1,0) Number of steps = 6 Total effort = 24 +++ Minimum total combined effort --- Allowing robots to share a node Steps: (0,1) (9,4) (0,2) (9,5) (0,4) (9,2) (0,9) (1,0) Number of steps = 7 Total effort = 22 --- Disallowing robots to share a node Steps: (0,1) (9,4) (0,2) (9,5) (0,4) (9,2) (0,9) (1,0) Number of steps = 7 Total effort = 22 ********* EXAMPLE 4 ********* n = 10 m = 9 +++ Path lengths: 1 2 1 1 3 3 3 1 2 1 +++ Edges: ( 1, 9) ( 7, 8) ( 1, 7) ( 0, 6) ( 3, 5) ( 3, 4) ( 1, 3) ( 0, 2) ( 0, 1) +++ Input graph Number of vertices: 10 Number of edges : 9 0 (1) -> 1, 2, 6 1 (2) -> 0, 3, 7, 9 2 (1) -> 0 3 (1) -> 1, 4, 5 4 (3) -> 3 5 (3) -> 3 6 (3) -> 0 7 (1) -> 1, 8 8 (2) -> 7 9 (1) -> 1 +++ Reachability graph Number of vertices: 10 Number of edges : 25 0 (1) -> 1, 2, 6 1 (2) -> 2, 4, 5, 6, 8 2 (1) -> 0 3 (1) -> 1, 4, 5 4 (3) -> 0, 7, 9 5 (3) -> 0, 7, 9 6 (3) -> 3, 7, 9 7 (1) -> 1, 8 8 (2) -> 1 9 (1) -> 1 +++ Simultaneous reachability graph Number of vertices: 100 Number of edges : 625 0 (2) -> 66, 62, 61, 26, 22, 21, 16, 12, 11 1 (3) -> 68, 66, 65, 64, 62, 28, 26, 25, 24, 22, 18, 16, 15, 14, 12 2 (2) -> 60, 20, 10 3 (2) -> 65, 64, 61, 25, 24, 21, 15, 14, 11 4 (4) -> 69, 67, 60, 29, 27, 20, 19, 17, 10 5 (4) -> 69, 67, 60, 29, 27, 20, 19, 17, 10 6 (4) -> 69, 67, 63, 29, 27, 23, 19, 17, 13 7 (2) -> 68, 61, 28, 21, 18, 11 8 (3) -> 61, 21, 11 9 (2) -> 61, 21, 11 10 (3) -> 86, 82, 81, 66, 62, 61, 56, 52, 51, 46, 42, 41, 26, 22, 21 11 (4) -> 88, 86, 85, 84, 82, 68, 66, 65, 64, 62, 58, 56, 55, 54, 52, 48, 46, 45, 44, 42, 28, 26, 25, 24, 22 12 (3) -> 80, 60, 50, 40, 20 13 (3) -> 85, 84, 81, 65, 64, 61, 55, 54, 51, 45, 44, 41, 25, 24, 21 14 (5) -> 89, 87, 80, 69, 67, 60, 59, 57, 50, 49, 47, 40, 29, 27, 20 15 (5) -> 89, 87, 80, 69, 67, 60, 59, 57, 50, 49, 47, 40, 29, 27, 20 16 (5) -> 89, 87, 83, 69, 67, 63, 59, 57, 53, 49, 47, 43, 29, 27, 23 17 (3) -> 88, 81, 68, 61, 58, 51, 48, 41, 28, 21 18 (4) -> 81, 61, 51, 41, 21 19 (3) -> 81, 61, 51, 41, 21 20 (2) -> 6, 2, 1 21 (3) -> 8, 6, 5, 4, 2 22 (2) -> 0 23 (2) -> 5, 4, 1 24 (4) -> 9, 7, 0 25 (4) -> 9, 7, 0 26 (4) -> 9, 7, 3 27 (2) -> 8, 1 28 (3) -> 1 29 (2) -> 1 30 (2) -> 56, 52, 51, 46, 42, 41, 16, 12, 11 31 (3) -> 58, 56, 55, 54, 52, 48, 46, 45, 44, 42, 18, 16, 15, 14, 12 32 (2) -> 50, 40, 10 33 (2) -> 55, 54, 51, 45, 44, 41, 15, 14, 11 34 (4) -> 59, 57, 50, 49, 47, 40, 19, 17, 10 35 (4) -> 59, 57, 50, 49, 47, 40, 19, 17, 10 36 (4) -> 59, 57, 53, 49, 47, 43, 19, 17, 13 37 (2) -> 58, 51, 48, 41, 18, 11 38 (3) -> 51, 41, 11 39 (2) -> 51, 41, 11 40 (4) -> 96, 92, 91, 76, 72, 71, 6, 2, 1 41 (5) -> 98, 96, 95, 94, 92, 78, 76, 75, 74, 72, 8, 6, 5, 4, 2 42 (4) -> 90, 70, 0 43 (4) -> 95, 94, 91, 75, 74, 71, 5, 4, 1 44 (6) -> 99, 97, 90, 79, 77, 70, 9, 7, 0 45 (6) -> 99, 97, 90, 79, 77, 70, 9, 7, 0 46 (6) -> 99, 97, 93, 79, 77, 73, 9, 7, 3 47 (4) -> 98, 91, 78, 71, 8, 1 48 (5) -> 91, 71, 1 49 (4) -> 91, 71, 1 50 (4) -> 96, 92, 91, 76, 72, 71, 6, 2, 1 51 (5) -> 98, 96, 95, 94, 92, 78, 76, 75, 74, 72, 8, 6, 5, 4, 2 52 (4) -> 90, 70, 0 53 (4) -> 95, 94, 91, 75, 74, 71, 5, 4, 1 54 (6) -> 99, 97, 90, 79, 77, 70, 9, 7, 0 55 (6) -> 99, 97, 90, 79, 77, 70, 9, 7, 0 56 (6) -> 99, 97, 93, 79, 77, 73, 9, 7, 3 57 (4) -> 98, 91, 78, 71, 8, 1 58 (5) -> 91, 71, 1 59 (4) -> 91, 71, 1 60 (4) -> 96, 92, 91, 76, 72, 71, 36, 32, 31 61 (5) -> 98, 96, 95, 94, 92, 78, 76, 75, 74, 72, 38, 36, 35, 34, 32 62 (4) -> 90, 70, 30 63 (4) -> 95, 94, 91, 75, 74, 71, 35, 34, 31 64 (6) -> 99, 97, 90, 79, 77, 70, 39, 37, 30 65 (6) -> 99, 97, 90, 79, 77, 70, 39, 37, 30 66 (6) -> 99, 97, 93, 79, 77, 73, 39, 37, 33 67 (4) -> 98, 91, 78, 71, 38, 31 68 (5) -> 91, 71, 31 69 (4) -> 91, 71, 31 70 (2) -> 86, 82, 81, 16, 12, 11 71 (3) -> 88, 86, 85, 84, 82, 18, 16, 15, 14, 12 72 (2) -> 80, 10 73 (2) -> 85, 84, 81, 15, 14, 11 74 (4) -> 89, 87, 80, 19, 17, 10 75 (4) -> 89, 87, 80, 19, 17, 10 76 (4) -> 89, 87, 83, 19, 17, 13 77 (2) -> 88, 81, 18, 11 78 (3) -> 81, 11 79 (2) -> 81, 11 80 (3) -> 16, 12, 11 81 (4) -> 18, 16, 15, 14, 12 82 (3) -> 10 83 (3) -> 15, 14, 11 84 (5) -> 19, 17, 10 85 (5) -> 19, 17, 10 86 (5) -> 19, 17, 13 87 (3) -> 18, 11 88 (4) -> 11 89 (3) -> 11 90 (2) -> 16, 12, 11 91 (3) -> 18, 16, 15, 14, 12 92 (2) -> 10 93 (2) -> 15, 14, 11 94 (4) -> 19, 17, 10 95 (4) -> 19, 17, 10 96 (4) -> 19, 17, 13 97 (2) -> 18, 11 98 (3) -> 11 99 (2) -> 11 s = 8 t = 9 +++ Minimum number of steps --- Allowing robots to share a node Steps: (8,9) (1,1) (8,6) (1,9) (6,1) (9,8) Number of steps = 5 Total effort = 20 --- Disallowing robots to share a node The puzzle is not solvable +++ Minimum total combined effort --- Allowing robots to share a node Steps: (8,9) (1,1) (2,2) (0,0) (6,1) (9,8) Number of steps = 5 Total effort = 16 --- Disallowing robots to share a node The puzzle is not solvable ********* EXAMPLE 5 ********* n = 10 m = 12 +++ Path lengths: 2 1 3 2 2 1 1 1 3 1 +++ Edges: ( 8, 9) ( 3, 8) ( 3, 7) ( 5, 6) ( 3, 5) ( 0, 4) ( 2, 3) ( 0, 2) ( 0, 1) ( 1, 3) ( 2, 4) ( 4, 7) +++ Input graph Number of vertices: 10 Number of edges : 12 0 (2) -> 1, 2, 4 1 (1) -> 3, 0 2 (3) -> 4, 0, 3 3 (2) -> 1, 2, 5, 7, 8 4 (2) -> 7, 2, 0 5 (1) -> 3, 6 6 (1) -> 5 7 (1) -> 4, 3 8 (3) -> 3, 9 9 (1) -> 8 +++ Reachability graph Number of vertices: 10 Number of edges : 30 0 (2) -> 2, 3, 4, 7 1 (1) -> 0, 3 2 (3) -> 0, 1, 3, 4, 6, 7, 9 3 (2) -> 0, 4, 6, 9 4 (2) -> 0, 1, 2, 3 5 (1) -> 3, 6 6 (1) -> 5 7 (1) -> 3, 4 8 (3) -> 0, 4, 6 9 (1) -> 8 +++ Simultaneous reachability graph Number of vertices: 100 Number of edges : 900 0 (4) -> 77, 74, 73, 72, 47, 44, 43, 42, 37, 34, 33, 32, 27, 24, 23, 22 1 (3) -> 73, 70, 43, 40, 33, 30, 23, 20 2 (5) -> 79, 77, 76, 74, 73, 71, 70, 49, 47, 46, 44, 43, 41, 40, 39, 37, 36, 34, 33, 31, 30, 29, 27, 26, 24, 23, 21, 20 3 (4) -> 79, 76, 74, 70, 49, 46, 44, 40, 39, 36, 34, 30, 29, 26, 24, 20 4 (4) -> 73, 72, 71, 70, 43, 42, 41, 40, 33, 32, 31, 30, 23, 22, 21, 20 5 (3) -> 76, 73, 46, 43, 36, 33, 26, 23 6 (3) -> 75, 45, 35, 25 7 (3) -> 74, 73, 44, 43, 34, 33, 24, 23 8 (5) -> 76, 74, 70, 46, 44, 40, 36, 34, 30, 26, 24, 20 9 (3) -> 78, 48, 38, 28 10 (3) -> 37, 34, 33, 32, 7, 4, 3, 2 11 (2) -> 33, 30, 3, 0 12 (4) -> 39, 37, 36, 34, 33, 31, 30, 9, 7, 6, 4, 3, 1, 0 13 (3) -> 39, 36, 34, 30, 9, 6, 4, 0 14 (3) -> 33, 32, 31, 30, 3, 2, 1, 0 15 (2) -> 36, 33, 6, 3 16 (2) -> 35, 5 17 (2) -> 34, 33, 4, 3 18 (4) -> 36, 34, 30, 6, 4, 0 19 (2) -> 38, 8 20 (5) -> 97, 94, 93, 92, 77, 74, 73, 72, 67, 64, 63, 62, 47, 44, 43, 42, 37, 34, 33, 32, 17, 14, 13, 12, 7, 4, 3, 2 21 (4) -> 93, 90, 73, 70, 63, 60, 43, 40, 33, 30, 13, 10, 3, 0 22 (6) -> 99, 97, 96, 94, 93, 91, 90, 79, 77, 76, 74, 73, 71, 70, 69, 67, 66, 64, 63, 61, 60, 49, 47, 46, 44, 43, 41, 40, 39, 37, 36, 34, 33, 31, 30, 19, 17, 16, 14, 13, 11, 10, 9, 7, 6, 4, 3, 1, 0 23 (5) -> 99, 96, 94, 90, 79, 76, 74, 70, 69, 66, 64, 60, 49, 46, 44, 40, 39, 36, 34, 30, 19, 16, 14, 10, 9, 6, 4, 0 24 (5) -> 93, 92, 91, 90, 73, 72, 71, 70, 63, 62, 61, 60, 43, 42, 41, 40, 33, 32, 31, 30, 13, 12, 11, 10, 3, 2, 1, 0 25 (4) -> 96, 93, 76, 73, 66, 63, 46, 43, 36, 33, 16, 13, 6, 3 26 (4) -> 95, 75, 65, 45, 35, 15, 5 27 (4) -> 94, 93, 74, 73, 64, 63, 44, 43, 34, 33, 14, 13, 4, 3 28 (6) -> 96, 94, 90, 76, 74, 70, 66, 64, 60, 46, 44, 40, 36, 34, 30, 16, 14, 10, 6, 4, 0 29 (4) -> 98, 78, 68, 48, 38, 18, 8 30 (4) -> 97, 94, 93, 92, 67, 64, 63, 62, 47, 44, 43, 42, 7, 4, 3, 2 31 (3) -> 93, 90, 63, 60, 43, 40, 3, 0 32 (5) -> 99, 97, 96, 94, 93, 91, 90, 69, 67, 66, 64, 63, 61, 60, 49, 47, 46, 44, 43, 41, 40, 9, 7, 6, 4, 3, 1, 0 33 (4) -> 99, 96, 94, 90, 69, 66, 64, 60, 49, 46, 44, 40, 9, 6, 4, 0 34 (4) -> 93, 92, 91, 90, 63, 62, 61, 60, 43, 42, 41, 40, 3, 2, 1, 0 35 (3) -> 96, 93, 66, 63, 46, 43, 6, 3 36 (3) -> 95, 65, 45, 5 37 (3) -> 94, 93, 64, 63, 44, 43, 4, 3 38 (5) -> 96, 94, 90, 66, 64, 60, 46, 44, 40, 6, 4, 0 39 (3) -> 98, 68, 48, 8 40 (4) -> 37, 34, 33, 32, 27, 24, 23, 22, 17, 14, 13, 12, 7, 4, 3, 2 41 (3) -> 33, 30, 23, 20, 13, 10, 3, 0 42 (5) -> 39, 37, 36, 34, 33, 31, 30, 29, 27, 26, 24, 23, 21, 20, 19, 17, 16, 14, 13, 11, 10, 9, 7, 6, 4, 3, 1, 0 43 (4) -> 39, 36, 34, 30, 29, 26, 24, 20, 19, 16, 14, 10, 9, 6, 4, 0 44 (4) -> 33, 32, 31, 30, 23, 22, 21, 20, 13, 12, 11, 10, 3, 2, 1, 0 45 (3) -> 36, 33, 26, 23, 16, 13, 6, 3 46 (3) -> 35, 25, 15, 5 47 (3) -> 34, 33, 24, 23, 14, 13, 4, 3 48 (5) -> 36, 34, 30, 26, 24, 20, 16, 14, 10, 6, 4, 0 49 (3) -> 38, 28, 18, 8 50 (3) -> 67, 64, 63, 62, 37, 34, 33, 32 51 (2) -> 63, 60, 33, 30 52 (4) -> 69, 67, 66, 64, 63, 61, 60, 39, 37, 36, 34, 33, 31, 30 53 (3) -> 69, 66, 64, 60, 39, 36, 34, 30 54 (3) -> 63, 62, 61, 60, 33, 32, 31, 30 55 (2) -> 66, 63, 36, 33 56 (2) -> 65, 35 57 (2) -> 64, 63, 34, 33 58 (4) -> 66, 64, 60, 36, 34, 30 59 (2) -> 68, 38 60 (3) -> 57, 54, 53, 52 61 (2) -> 53, 50 62 (4) -> 59, 57, 56, 54, 53, 51, 50 63 (3) -> 59, 56, 54, 50 64 (3) -> 53, 52, 51, 50 65 (2) -> 56, 53 66 (2) -> 55 67 (2) -> 54, 53 68 (4) -> 56, 54, 50 69 (2) -> 58 70 (3) -> 47, 44, 43, 42, 37, 34, 33, 32 71 (2) -> 43, 40, 33, 30 72 (4) -> 49, 47, 46, 44, 43, 41, 40, 39, 37, 36, 34, 33, 31, 30 73 (3) -> 49, 46, 44, 40, 39, 36, 34, 30 74 (3) -> 43, 42, 41, 40, 33, 32, 31, 30 75 (2) -> 46, 43, 36, 33 76 (2) -> 45, 35 77 (2) -> 44, 43, 34, 33 78 (4) -> 46, 44, 40, 36, 34, 30 79 (2) -> 48, 38 80 (5) -> 67, 64, 63, 62, 47, 44, 43, 42, 7, 4, 3, 2 81 (4) -> 63, 60, 43, 40, 3, 0 82 (6) -> 69, 67, 66, 64, 63, 61, 60, 49, 47, 46, 44, 43, 41, 40, 9, 7, 6, 4, 3, 1, 0 83 (5) -> 69, 66, 64, 60, 49, 46, 44, 40, 9, 6, 4, 0 84 (5) -> 63, 62, 61, 60, 43, 42, 41, 40, 3, 2, 1, 0 85 (4) -> 66, 63, 46, 43, 6, 3 86 (4) -> 65, 45, 5 87 (4) -> 64, 63, 44, 43, 4, 3 88 (6) -> 66, 64, 60, 46, 44, 40, 6, 4, 0 89 (4) -> 68, 48, 8 90 (3) -> 87, 84, 83, 82 91 (2) -> 83, 80 92 (4) -> 89, 87, 86, 84, 83, 81, 80 93 (3) -> 89, 86, 84, 80 94 (3) -> 83, 82, 81, 80 95 (2) -> 86, 83 96 (2) -> 85 97 (2) -> 84, 83 98 (4) -> 86, 84, 80 99 (2) -> 88 s = 5 t = 8 +++ Minimum number of steps --- Allowing robots to share a node Steps: (5,8) (6,6) (5,5) (3,3) (9,6) (8,5) Number of steps = 5 Total effort = 14 --- Disallowing robots to share a node Steps: (5,8) (6,4) (5,0) (3,2) (9,6) (8,5) Number of steps = 5 Total effort = 17 +++ Minimum total combined effort --- Allowing robots to share a node Steps: (5,8) (6,6) (5,5) (3,3) (9,6) (8,5) Number of steps = 5 Total effort = 14 --- Disallowing robots to share a node Steps: (5,8) (3,6) (6,5) (5,6) (3,5) (9,6) (8,5) Number of steps = 6 Total effort = 16