Undirected determinant and its complexity

DOI10.1007/S00373-023-02671-7MaRDI QIDQ6166664zbMATH OpenOpenAlexFDO

Authors Diana Dziewa-Dawidczyk, Adam J. Przeździecki

Publication date 3 August 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2108.13090

zbMATH Keywords

computational complexitydeterminantenumerative combinatoricsPfaffian orientationplanar graphsundirected permanent

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We view the determinant and permanent as functions on directed weighted graphs and introduce their analogues for the undirected graphs. We prove that the task of computing the undirected determinants as well as permanents for planar graphs, whose vertices have degree at most 4, is #P-complete. In the case of planar graphs whose vertices have degree at most 3, the computation of the undirected determinant remains #P-complete while the permanent can be reduced to the FKT algorithm, and therefore is polynomial. The undirected permanent is a Holant problem and its complexity can be deduced from the existing literature. The concept of the undirected determinant is new. Its introduction is motivated by the formal resemblance to the directed determinant, a property that may inspire generalizations of some of the many algorithms which compute the latter. For a sizable class of planar 3-regular graphs, we are able to compute the undirected determinant in polynomial time.

Recommendations

• On the complexity of computing determinants
• scientific article; zbMATH DE number 1332669
• Complexity metric and structural measure on the class of deterministic matrices
• Parameterized complexity of determinant and permanent
• A lower bound on determinantal complexity
• A lower bound on determinantal complexity
• On the determinant of a uniformly distributed complex matrix
• Complexity metric and structural measure on the class of non deterministic matrices
• On the complexity of approximating extremal determinants in matrices
• Complexity of constructing Dixon resultant matrix

Cites work

• A survey of Pfaffian orientations of graphs
• Almost settling the hardness of noncommutative determinant
• Determinant versus permanent: salvation via generalization?
• Dimer problem in statistical mechanics-an exact result
• Expressiveness of matchgates.
• Holographic Algorithms
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 1775055 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Matchgates revisited
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of the fermionant and immanants of constant width
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(2)

• Planarity, determinants, permanents, and (unique) matchings
• Planarity, Determinants, Permanents, and (Unique) Matchings

This page was built for publication: Undirected determinant and its complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166664)