On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

DOI10.1007/S00224-009-9241-3MaRDI QIDQ987381zbMATH OpenOpenAlexFDO

Authors Uffe Flarup, Laurent Lyaudet

Publication date 13 August 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

algebraic complexitycycle coverHamiltonianperfect matchingpermanenttopological pathwidthValiant's modelweighted cliquewidth

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) includes the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the expressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matrices of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.

Recommendations

• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• Tree-width in algebraic complexity
• On the expressive power of CNF formulas of bounded tree- and clique-width

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Characterizing Valiant’s Algebraic Complexity Classes
• Compact Forbidden-Set Routing
• Computing Algebraic Formulas Using a Constant Number of Registers
• Dimer problem in statistical mechanics-an exact result
• scientific article; zbMATH DE number 177438 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 1859215 (Why is no real title available?)
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• On the Relationship Between Clique-Width and Treewidth
• Statistical Mechanics of Dimers on a Plane Lattice
• The complexity of computing the permanent
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Upper bounds to the clique width of graphs

Cited in

(11)

• Small space analogues of Valiant's classes and the limitations of skew formulas
• An extended tree-width notion for directed graphs related to the computation of permanents
• On hard instances of non-commutative permanent
• The rank-width of edge-coloured graphs
• On hard instances of non-commutative permanent
• An extended tree-width notion for directed graphs related to the computation of permanents
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• F-rank-width of (edge-colored) graphs
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices

This page was built for publication: On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

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