Bipartite Perfect Matching bipartite graph perfect matchings 三凶 G([n],[n],E) permutationπof[n]s.t.(i,π(i)∈E m×m matrix A: of P.M.in G A,= 1(i,)∈E (i,)E ∑ΠA,同 π∈Sni∈[nl
Bipartite Perfect Matching 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand 4 Perfect matchings in bipartite graphs. Consider a bipartite graph with bipartition (N,N), where N = {1,...,n}, and edge set E ⊆ N × N. A perfect matching is an edge subset M ⊆ E that includes every node as an endpoint exactly once. See Fig. 3 for some interpretations. Fig. 3. Row 1: A bipartite graph and its three perfect matchings. Row 2: In the graph’s adjacency matrix A, every perfect matching corresponds to a permutation π for which Ai,π(i) = 1 for all i ∈ [n]. Row 3: In the directed n-node graph defined by A, every perfect matching corresponds to a directed cycle partition. Bottom row: an equivalent formulation in terms of non-attacking rooks on a chess board with forbidden positions. 111 110 011 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 3 2 1 3 2 1 3 2 1 3 2 VR VR VR VR VR VR VR VR VR The Ryser formula for counting the perfect matchings in such a graph can be given as ! π∈Sn " n i=1 [iπ(i) ∈ E] = ! S⊆N (−1)|N\S| " n i=1 ! j∈S [ij ∈ E] , (4) where Sn denotes the set of permutations from N to N. The left hand side succinctly describes the problem as iterating over all permutations and checking if the corresponding edges (namely, 1π(1), 2π(2), ..., nπ(n)) are all in E. Direct evaluation would require n! iterations. The right hand side provides an equivalent expression that can be evaluated in time O(2nn2), see Fig. 4. Proof of (4). For fixed i ∈ N, the value # j∈S [ij ∈ E] counts the number of i’s neighbours in S ⊆ N. Thus the expression " n i=1 ! j∈S [ij ∈ E] (5) is the number of ways every node i ∈ N can choose a neighbour from S. (This allows some nodes to select the same neighbour.) Consider such a choice as a mapping g : N → N, not necessarily onto, with image R = g(N). The contribution of g to (5) is 1 for every S ⊇ R, and its total contribution to the right hand bipartite graph G([n],[n],E) perfect matchings permutation of [n] s.t. (i, (i)) E Ai,j = 1 (i, j) E 0 (i, j) E n n matrix A : = Sn i[n] Ai,(i) # of P.M. in G
Permanent m×n matrix A: Derm(A)=∑IA,m(O π∈Sni∈[nl #P-hard to compute determinant: det(A)=∑(-1)r)IA.ma π∈Sn iEln] poly-time by Gaussian elimination
Permanent n n matrix A : = Sn i[n] perm(A) Ai,(i) det(A) = Sn (1)r() i[n] Ai,(i) determinant: poly-time by Gaussian elimination #P-hard to compute