Permanents, Pfaffian orientations, and even directed circuits
From MaRDI portal
Publication:1971908
DOI10.2307/121059zbMATH Open0947.05066arXivmath/9911268OpenAlexW2064153357MaRDI QIDQ1971908FDOQ1971908
Neil Robertson, Paul Seymour, Robin Thomas
Publication date: 23 March 2000
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: Given a 0-1 square matrix A, when can some of the 1's be changed to -1's in such a way that the permanent of A equals the determinant of the modified matrix? When does a real square matrix have the property that every real matrix with the same sign pattern (that is, the corresponding entries either have the same sign or are both zero) is nonsingular? When is a hypergraph with n vertices and n hyperedges minimally nonbipartite? When does a bipartite graph have a "Pfaffian orientation"? Given a digraph, does it have no directed circuit of even length? Given a digraph, does it have a subdivision with no even directed circuit? It is known that all of the above problems are equivalent. We prove a structural characterization of the feasible instances, which implies a polynomial-time algorithm to solve all of the above problems. The structural characterization says, roughly speaking, that a bipartite graph has a Pfaffian orientation if and only if it can be obtained by piecing together (in a specified way) planar bipartite graphs and one sporadic nonplanar bipartite graph.
Full work available at URL: https://arxiv.org/abs/math/9911268
determinantcharacterizationpolynomial-time algorithmpermanentPfaffian orientations[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=P%EF%BF%BD%EF%BF%BDlya+matrix&go=Go P��lya matrix]
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)
Cited In (95)
- Augmenting tractable fragments of abstract argumentation
- Odd \(K_{3,3}\) subdivisions in bipartite graphs
- Synchronizing Boolean networks asynchronously
- On the dimer problem of the vertex-edge graph of a cubic graph
- On the Number of α-Orientations
- On the Pólya permanent problem over finite fields
- Some results on injectivity and multistationarity in chemical reaction networks
- Finding kernels or solving SAT
- On spanning galaxies in digraphs
- Some results on the structure and spectra of matrix-products
- A characterisation of Pfaffian near bipartite graphs
- On the skew-permanental polynomials of orientation graphs
- On the hardness of efficiently approximating maximal non-\(L\) submatrices.
- On the even permutation polytope
- Brace generation
- The characteristic polynomial and the matchings polynomial of a weighted oriented graph
- Generating bricks
- Complexity of fixed point counting problems in Boolean networks
- Finding a path with two labels forbidden in group-labeled graphs
- Minimally non-Pfaffian graphs
- Dimers on the \(3^3 . 4^2\) lattice
- 2-extendability of toroidal polyhexes and Klein-bottle polyhexes
- Binary linear codes, dimers and hypermatrices
- 2-factor Hamiltonian graphs.
- The combinatorics of N. G. de Bruijn
- A generalization of Little's theorem on Pfaffian orientations
- Positive and negative cycles in Boolean networks
- A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
- Convertible subspaces of Hessenberg-type matrices
- On the complexity of feedback set problems in signed digraphs
- Max-algebra: The linear algebra of combinatorics?
- Regular bipartite graphs with all 2-factors isomorphic
- Thin edges in braces
- Computing the inertia from sign patterns
- Matching signatures and Pfaffian graphs
- Solving linear programs from sign patterns
- Sign-solvable linear complementarity problems
- Pfaffian orientations for a type of bipartite graph
- Oriented Euler complexes and signed perfect matchings
- On the permanental polynomials of matrices
- Polynomial recognition of equal unions in hypergraphs with few vertices of large degree
- The Pfaffian property of circulant graphs
- Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem
- Computing Maximal Autarkies with Few and Simple Oracle Queries
- Equilibria of graphical games with symmetries
- Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals
- Backdoors to Satisfaction
- Enumeration of perfect matchings of a type of Cartesian products of graphs
- A quadratic identity for the number of perfect matchings of plane graphs
- A sufficient condition for Pfaffian graphs on the torus
- A new proof of a characterisation of Pfaffian bipartite graphs
- Matching connectivity: on the structure of graphs with perfect matchings
- Face-width of Pfaffian braces and polyhex graphs on surfaces
- Backdoors to tractable answer set programming
- A note on the parity assignment problem
- Even cycles and perfect matchings in claw-free plane graphs
- Minimum \(k\)-critical bipartite graphs
- An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
- Packing directed circuits exactly
- Odd properly colored cycles in edge-colored graphs
- Pfaffian orientations and perfect matchings of scale-free networks
- Pfaffian graphs embedding on the torus
- Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
- Recognizing near-bipartite Pfaffian graphs in polynomial time
- The Pfaffian property of Cartesian products of graphs
- Matching theory and Barnette's conjecture
- On the number of dissimilar pfaffian orientations of graphs
- Strong orientations without even directed circuits
- Excluding a planar matching minor in bipartite graphs
- On essentially 4-edge-connected cubic bricks
- Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
- Threshold function of ray nonsingularity for uniformly random ray pattern matrices
- Graph characterization of fully indecomposable nonconvertible (0, 1)-matrices with minimal number of ones
- Minimal braces
- Arithmetic matrix operations that preserve conversion
- Lattice point of view for argumentation framework
- The Pfaffian property of Cayley graphs on dihedral groups
- Shortest odd paths in undirected graphs with conservative weight functions
- The Pfaffian property of graphs on the Möbius strip based on topological resolution
- PERFECT MATCHINGS AND GENUS OF SOME CARTESIAN PRODUCTS OF GRAPHS
- Counting the number of perfect matchings, and generalized decision trees
- Replacing Pfaffians and applications
- A matching-minor monotone parameter for bipartite graphs
- On the rank of a real skew symmetric matrix described by an oriented graph
- Even circuits in oriented matroids
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Colouring non-even digraphs
- Binary linear codes via 4D discrete Ihara-Selberg function
- Spanning galaxies in digraphs
- A conjecture of Norine and Thomas for abelian Cayley graphs
- Cache me if you can: capacitated selfish replication games in networks
- Out-degree reducing partitions of digraphs
- Enumeration of perfect matchings of the Cartesian products of graphs
- Colouring non-even digraphs
- Pfaffian polyominos on the Klein bottle
This page was built for publication: Permanents, Pfaffian orientations, and even directed circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971908)
