On the complexity of a family of generalized matching problems (Q1068535)

We consider a family of generalized matching problems called k-feasible matching (k-FM) problems, where \(k\in \{1,2,3,...\}\cup \{\infty \}\). We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of \(\{\) 1,2,...\(\}\) \(\cup \{\infty \}\), there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.