On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth (extended abstract).

*(English)*Zbl 1142.68350
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 180-193 (2008).

Summary: 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 [“On the expressive power of planar perfect matching and permanents of bounded treewidth matrices”, Lect. Notes Comput. Sci. 4835, 124–136 (2007; Zbl 1141.68418)] 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.

For the entire collection see [Zbl 1136.68005].

In a previous paper [“On the expressive power of planar perfect matching and permanents of bounded treewidth matrices”, Lect. Notes Comput. Sci. 4835, 124–136 (2007; Zbl 1141.68418)] 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.

For the entire collection see [Zbl 1136.68005].

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |