Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width

Abstract

In this paper, we provide polynomial-time algorithms for different extensions of the matching counting problem, namely maximal matchings, path matchings (linear forest) and paths, on graph classes of bounded clique-width. For maximal matchings, we introduce matching-cover pairs to efficiently handle maximality in the local structure, and develop a polynomial time algorithm. For path matchings, we develop a way to classify the path matchings in a polynomial number of equivalent classes. Using these, we develop dynamic programing algorithms that run in polynomial time of the graph size, but in exponential time of the clique-width. In particular, we show that for a graph $G$ of $n$ vertices and clique-width $k$, these problems can be solved in $O(n^{f(k)})$ time where $f$ is exponential in $k$ or in $O(n^g(l))$ time where $g$ is linear or quadratic in $l$ if an $l$-expression for $G$ is given as input.

10 pages, with a 3-page appendix