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

摘要

In this paper, we provide polynomial-time algorithms for dif ferent 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~9(l)) time where g is linear or quadratic in l if an l-expression for G is given as input.