Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs (Q911300)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs |
scientific article |
Statements
Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs (English)
0 references
1989
0 references
The problem of whether one can change some \(+1\) into -1 of a (0,1) matrix A so that the determinant of the resultant matrix equals the permanent of A is proved to be polynomial-time equivalent to the problem of determining whether a directed graph has an even length simple cycle. The problem of determining whether a graph has a Pfaffian orientation is proved to be polynomial-time equivalent to the problem whether a given orientation of a graph is Pfaffian. Both problems are actually in Co-NP. Let A be a an \(n\times n\) integer matrix. The problem \(``\det (A)=perm(A)?''\) is NP-hard. It is polynomial-time equivalent to the problem of even cycles if A is a (0,1) matrix.
0 references
even cycles
0 references
permanent
0 references
Pfaffian orientation
0 references