导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

摘要

图G的一个匹配M是导出的,若M是图G的一个导出子图. 图G是导出匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中.本文我们将证明如下结果. (1)对无爪图而言,问题"给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得|M|≥r"是NP-完全的. (2)对直径为2的图以及直径为3的偶图,问题"确定一个给定图是否为导出匹配可扩的"是CO-NP-完全的;而对完全多部图而言,该问题线性可解.%A matching M of a graph G is induced, if M is an induced subgraph of G. A graph G is induced matching extendable (simply IM-extendable), if every induced matching M of G is included in a perfect matching of G. In this paper we will prove the following results. (1) The problem "given a graph G and a positive integer r, determine whether there is an induced matching M of G such that |M| ≥ r" is NP-complete for claw-free graphs. (2) The problem "determine whether a given graph is IM-extendable" is co-NP-complete for graphs with diameter 2 and bipartite graphs with diameter 3 but linearly solvable for complete multi-partite graphs.