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

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

Authors: Uffe Flarup, Laurent Lyaudet 

Publication date: 13 August 2010

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• 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
• An extended tree-width notion for directed graphs related to the computation of permanents
• On Hard Instances of Non-Commutative Permanent
• \(\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)