Computing the Permanent of a Matrix - Some Inclusion-Exclusion Algorithms

4.2 Some Inclusion-Exclusion Algorithms

4.2.1 Computing the Permanent of a Matrix

LetA= [a_{i j}],i,j∈ {1, . . . ,n}, be a binaryn×nmatrix, i.e. a matrix in which each entryai jis either zero or one. An important characteristic of a matrix is its perma-nentdefined as

perm(A) =

∑

π∈Sn

∏

i=1

a_i,π(i),

whereS_nis the set of all permutations of{1, . . . ,n}. For example, the permanent of matrix



a₁₁a₁₂ a₁₃ a₂₁a₂₂ a₂₃ a₃₁a₃₂ a₃₃





perm(A) =a11a22a33+a11a32a23+a21a12a33+a₂₁a32a13

+a₃₁a₁₂a₂₃+a₃₁a₂₂a₁₃.

While the formula of the permanent looks very similar to the formula of the de-terminant, the computational complexity of these two characteristics is drastically different. The trivial algorithm computing the permanent of a matrix would be to try all possible permutationsπ, and compute for each permutation the corresponding sum, which results in running timeO^∗(n!).

Computing the permanent of a binary matrix can be expressed in the language of Graph Theory as a problem of counting perfect matchings in bipartite graphs.

A matching M of a graph G= (V,E) is perfect if M is an edge cover of G. In other words, every vertex ofGis incident to precisely one edge of M. Deciding whether a graph has a perfect matching is a classical combinatorial problem and is solvable in polynomial time. However, counting perfect matchings is known to be a

#P-complete problem.

LetG= (V,E)be a bipartite graph with bipartition(X,Y),X={x₁,x₂, . . . ,x_n}, Y ={y₁,y₂, . . . ,y_n}. LetA_G= [a_{i j}],i,j∈ {1, . . . ,n}be the adjacency matrix ofG, then×nbinary matrix whose entrya_{i j}is 1 if{x_i,y_j} ∈Eand 0 otherwise. Let us define the characteristic function

f(x_i,y_j) =

(1 if{xi,yj} ∈E, 0 otherwise.

Then the number of perfect matchings inGis equal to

∑

π∈Sn

∏

i=1

f(x_i,y_π(i)).

The main observation here is that for every permutation π ∈S_n, a set of edges M ={{x₁,y_π(1)},{x₂,y_π(2)}, . . . ,{x_n,y_π(n)}} is a perfect matching if and only if a_1π(1)a_2π(2)···a_nπ(n)=1. Thus the number of perfect matchings inGis equal to

∑

π∈Sn

∏

i=1

a_iπ(i)=perm(A^G).

An example is given in Fig. 4.1.

Using inclusion-exclusion and the scenario of Theorem 4.2 we prove the follow-ing lemma.

4.2 Some Inclusion-Exclusion Algorithms 55

58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

x₁ x2

Directed Hamiltonian s, t-Path In the Directed Hamiltonian s, t-Path problem we are given a directed and simple graphG = (V, E) with vertex set{s, t} ∪ {v₁, v₂, . . . , v_n}and edge setE. The task is to determine whether there is a hamiltonian path fromstotinG, i.e. a directed pathP = (s, . . . , t) of lengthn+ 1 inGsuch that each vertex ofGoccurs precisely once inP.

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5.The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths fromstotinG. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to t of length n+ 1. A directed walk from s to t of length n+ 1 is a sequences, v1, ..., vn, tof vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has propertyQ(i) if it contains vertexvi. Hence for every subsetW ⊆ {1,2, . . . , n},N(W) is the number of objects having none of the propertiesQ(i), for all i ∈ W. In other words, N(W) is the number of directed walks of lengthn+ 1 fromsto tcontaining no vertex v_i withi∈W. We defineX to be the number of directed walks of length n+ 1 containing all vertices of {v₁, v₂, . . . v_n}. Thus X is the number of hamiltonian paths fromstot. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X= �

W⊆{1,2,...,n}

(−1)^|W^|N(W). (4.3) 58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

Directed Hamiltonian s, t-Path In the Directed Hamiltonian s, t-Path problem we are given a directed and simple graphG = (V, E) with vertex set{s, t} ∪ {v1, v2, . . . , vn}and edge setE. The task is to determine whether there is a hamiltonian path fromstotinG, i.e. a directed pathP = (s, . . . , t) of lengthn+ 1 inGsuch that each vertex ofGoccurs precisely once inP.

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5.The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths fromstotinG. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to t of length n+ 1. A directed walk from s to t of length n+ 1 is a sequences, v1, ..., vn, tof vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has propertyQ(i) if it contains vertexvi. Hence for every subsetW ⊆ {1,2, . . . , n},N(W) is the number of objects having none of the propertiesQ(i), for all i ∈ W. In other words, N(W) is the number of directed walks of lengthn+ 1 fromsto tcontaining no vertex vi withi∈W. We defineX to be the number of directed walks of length n+ 1 containing all vertices of {v1, v2, . . . vn}. Thus X is the number of hamiltonian paths fromstot. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X= �

W⊆{1,2,...,n}

(−1)^|W^|N(W). (4.3)

58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

Directed Hamiltonian s, t-Path In theDirected Hamiltonian s, t-Path problem we are given a directed and simple graphG= (V, E) with vertex set{s, t} ∪ {v1, v2, . . . , vn}and edge setE. The task is to determine whether there is a hamiltonian path fromstotinG, i.e. a directed pathP = (s, . . . , t) of lengthn+ 1 inGsuch that each vertex ofGoccurs precisely once inP.

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5. The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths fromstotinG. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to tof length n+ 1. A directed walk from s to t of length n+ 1 is a sequences, v₁, ..., v_n, tof vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has propertyQ(i) if it contains vertexvi. Hence for every subsetW ⊆ {1,2, . . . , n},N(W) is the number of objects having none of the properties Q(i), for all i ∈W. In other words, N(W) is the number of directed walks of lengthn+ 1 from sto tcontaining no vertex vi withi ∈W. We defineX to be the number of directed walks of length n+ 1 containing all vertices of {v1, v2, . . . vn}. ThusX is the number of hamiltonian paths fromstot. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X= �

W⊆{1,2,...,n}

(−1)^|W|N(W). (4.3)

58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

Directed Hamiltonian s, t-Path In the Directed Hamiltonian s, t-Path problem we are given a directed and simple graphG= (V, E) with vertex set{s, t} ∪ {v1, v2, . . . , vn}and edge setE. The task is to determine whether there is a hamiltonian path fromstotinG, i.e. a directed pathP = (s, . . . , t) of lengthn+ 1 inGsuch that each vertex ofGoccurs precisely once inP.

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5.The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths fromstotinG. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to t of length n+ 1. A directed walk from s to tof length n+ 1 is a sequences, v1, ..., vn, tof vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has propertyQ(i) if it contains vertexvi. Hence for every subsetW ⊆ {1,2, . . . , n},N(W) is the number of objects having none of the propertiesQ(i), for all i ∈ W. In other words,N(W) is the number of directed walks of lengthn+ 1 fromsto tcontaining no vertex vi withi∈W. We defineX to be the number of directed walks of length n+ 1 containing all vertices of {v1, v2, . . . vn}. Thus X is the number of hamiltonian paths fromstot. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X= �

W⊆{1,2,...,n}

(−1)^|W|N(W). (4.3) 58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

y₁ y₂ y₃ x3

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5.The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

X= �

W⊆{1,2,...,n}

(−1)^|W^|N(W). (4.3)

58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�n i=1

�

j�∈W

f(i, j)

is computable in polynomial time, and thus the running time required to compute the permanent isO^∗(2ⁿ).

Directed Hamiltonian s, t-Path In theDirected Hamiltonian s, t-Path problem we are given a directed and simple graphG= (V, E) with vertex set{s, t} ∪ {v1, v2, . . . , vn}and edge setE. The task is to determine whether there is a hamiltonian path fromstotinG, i.e. a directed pathP = (s, . . . , t) of lengthn+ 1 inGsuch that each vertex ofGoccurs precisely once inP.

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5. The number of directed hamiltonians, t-paths in a graph can be computed in timeO^∗(2ⁿ)and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths fromstotinG. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to tof length n+ 1. A directed walk from s to t of length n+ 1 is a sequences, v₁, ..., v_n, tof vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has propertyQ(i) if it contains vertexv_i. Hence for every subset W ⊆ {1,2, . . . , n},N(W) is the number of objects having none of the properties Q(i), for all i ∈W. In other words, N(W) is the number of directed walks of lengthn+ 1 from sto tcontaining no vertex vi withi ∈W. We define Xto be the number of directed walks of length n+ 1 containing all vertices of {v1, v2, . . . vn}. ThusX is the number of hamiltonian paths fromstot. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X= �

W⊆{1,2,...,n}

(−1)^|W|N(W). (4.3)

58 CHAPTER 4. INCLUSION-EXCLUSION

We comput permanent by making use of this formula. Each of the values

�

n i=1

�

j�∈W

f (i, j)

is computable in polynomial time, and thus the running time required to compute the permanent is O

^∗

(2

ⁿ

).

Directed Hamiltonian s, t-Path In the Directed Hamiltonian s, t-Path problem we are given a directed and simple graph G = (V, E ) with vertex set { s, t } ∪ { v

, v

, . . . , v

} and edge set E. The task is to determine whether there is a hamiltonian path from s to t in G, i.e. a directed path P = (s, . . . , t) of length n + 1 in G such that each vertex of G occurs precisely once in P .

To solve this decision problem the inclusion-exclusion algorithm actually solves a counting problem.

Theorem 4.5. The number of directed hamiltonian s, t-paths in a graph can be computed in time O

^∗

(2

ⁿ

) and in polynomial space.

Proof. To solve this decision problem we actually solve the corresponding counting problem. Our algorithm will determine the number of hamiltonian paths from s to t in G. To apply the inclusion-exclusion principle of counting, we use the scenario of Theorem 4.2. The objects are directed walks from s to t of length n + 1. A directed walk from s to t of length n + 1 is a sequence s, v

₁

, ..., v

, t of vertices such that every pair of consecutive vertices is connected by an edge; vertices and edges may show up repeatedly in a walk. A walk (or an object) has property Q(i) if it contains vertex v

. Hence for every subset W ⊆ { 1, 2, . . . , n } , N (W ) is the number of objects having none of the properties Q(i), for all i ∈ W . In other words, N(W ) is the number of directed walks of length n + 1 from s to t containing no vertex v

with i ∈ W . We define X to be the number of directed walks of length n + 1 containing all vertices of { v

₁

, v

₂

, . . . v

} . Thus X is the number of hamiltonian paths from s to t. By the inclusion-exclusion principle as given in Theorem 4.2, we have that

X = �

W⊆{1,2,...,n}

( − 1)

^|^W^|

N (W ). (4.3)

Fig. 4.1 A bipartite graphGand its adjacency matrix. The graphGhas two perfect matchings, namely,{x1,y1},{x2,y2},{x3,y3}and{x1,y1},{x2,y3},{x3,y2}. The permanent ofA^Gis 2.

Lemma 4.3.Let G be a bipartite graph and A^Gbe its adjacency matrix. Then perm(A^G) =

∑

Proof. Following the notation of Theorem 4.2, we define the collectionN of the following objects. Each objectM∈Nis a set ofnedges ofG, such that for every i∈ {1,2, . . . ,n}, the vertexx_iis an endpoint of some edge ofM. The propertyQ(j) is that the vertexy_j is an endpoint of some edge ofM. In this language, an object Mhas all propertiesQ(1),Q(2), . . . ,Q(n)iff it is a perfect matching ofG. ForW ⊆

Indeed, for every vertex x_i, to form an objectM, we can select exactly one edge with an endpointx_iwhose second endpoint is not inW. Now, by (4.2), the number X of objects having all properties, i.e. the number of perfect matchings inGor the permanent ofA^G, is equal to Putting all together, we obtain the following theorem.

Theorem 4.4.The permanent of a binary n×n matrix can be computed in time O^∗(2ⁿ)and polynomial space.

Proof. For a binary matrixA, we construct the bipartite graphG, such thatAis its adjacency matrix. Then by Lemma 4.3,

perm(A^G) =

∑

W⊆{1,2,...,n}

(−1)^|^W^|

∏

i=1

∑

j6∈W

f(i,j). (4.3)

We compute the permanent by making use of this formula. Each of the values

∏

i=1

∑

j6∈W

f(i,j)

is computable in polynomial time, and thus the running time required to compute

the permanent isO^∗(2ⁿ). ut

In document ExactExponentialAlgorithms FedorV.FominandDieterKratsch (sider 65-68)