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

DOI10.1007/S00224-009-9241-3zbMATH Open1197.68047OpenAlexW1988819200MaRDI QIDQ987381FDOQ987381

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

Hamiltonianperfect matchingpermanentalgebraic complexitycycle coverValiant's modeltopological pathwidthweighted cliquewidth

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the Relationship Between Clique-Width and Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• 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
• \(k\)-NLC graphs and polynomial algorithms

Cited In (11)

• Small space analogues of Valiant's classes and the limitations of skew formulas
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• On hard instances of non-commutative permanent
• An extended tree-width notion for directed graphs related to the computation of permanents
• An extended tree-width notion for directed graphs related to the computation of permanents
• \(\mathbb F\)-rank-width of (edge-colored) graphs
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• On hard instances of non-commutative permanent
• The rank-width of edge-coloured graphs
• 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

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)