Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Determinants, permanents, traces, other special matrix functions (15A15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
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.
- Characterization of even directed graphs
- Constructing a perfect matching is in random NC
- Even cycles in directed graphs
- Every 7-regular digraph contains an even cycle
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3517179 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- Matching is as easy as matrix inversion
- Matching structure and the matching lattice
- Matching theory
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- NP is as easy as detecting unique solutions
- On digraphs with the odd cycle property
- On the relation between the determinant and the permanent
- Sign-nonsingular matrices and even cycles in directed graphs
- Signsolvability revisited
- The complexity of computing the permanent
- Matching theory -- a sampler: From Dénes König to the present
- Extending matchings in graphs: A survey
- Strong orientations without even directed circuits
- Convertible subspaces of Hessenberg-type matrices
- The number of matrices with nonzero permanent over a finite field
- An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
- On the Gibson barrier for the Pólya problem
- A generalization of Little's theorem on Pfaffian orientations
- Permanents, Pfaffian orientations, and even directed circuits
- Colouring non-even digraphs
- Matching theory and Barnette's conjecture
- Arithmetic matrix operations that preserve conversion
- Oriented Euler complexes and signed perfect matchings
- Pfaffian orientations for a type of bipartite graph
- Minimal bricks
- Generating bricks
- Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals
- A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
- On the complexity of feedback set problems in signed digraphs
- scientific article; zbMATH DE number 4058868 (Why is no real title available?)
- The Even Cycle Problem for Directed Graphs
- scientific article; zbMATH DE number 1559555 (Why is no real title available?)
- On the number of dissimilar pfaffian orientations of graphs
- Face-width of Pfaffian braces and polyhex graphs on surfaces
- Even Orientations and Pfaffian graphs
- Permanents of \(3 \times 3\) invertible matrices modulo \(n\)
- The cubic vertices of minimal bricks
- Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem
- Minimal braces
- On the Pólya permanent problem over finite fields
- Minimum degree of minimal (n-10)-factor-critical graphs
- Shortest odd paths in undirected graphs with conservative weight functions
- K₄-free planar minimal bricks with the maximum number of edges
- Minimal bricks with the maximum number of edges
- A note on the 2-factor Hamiltonicity conjecture
- Spanning trees of 3-uniform hypergraphs
- The combinatorics of N. G. de Bruijn
- Computing the inertia from sign patterns
- Solving linear programs from sign patterns
- Sign-solvable linear complementarity problems
- Minimally non-Pfaffian graphs
- Pfaffian labelings and signs of edge colorings
- Recognizing near-bipartite Pfaffian graphs in polynomial time
This page was built for publication: Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911300)
