A matching is a set of edges in a graph with no common endpoint. A matching M is called acyclic if the induced subgraph on the endpoints of the edges in M is acyclic. Given a graph G and an integer k, Acyclic Matching Problem seeks for an acyclic matching of size k in G. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter k. On the other hand, the problem is fixed parameter tractable with respect to the parameters tw and (k, c4), where tw and c4 are the treewidth and the number of cycles with length 4 of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter k for the line graphs and every proper minor-closed class of graphs (including planar graphs).
翻译：匹配是一张没有共同端点的图形中的一组边缘。 如果 M 边缘端端端的诱导子图是环状的, 匹配 M 则称为“ 环状 ” 。 如果在 M 端端端端的诱导子图是环状的, 则匹配 M 称为“ 环状 ” 。 如果用一个图形 G 和一个整数 k, Acyclic 匹配问题会寻找 K 大小的环状匹配。 问题已知是 NP- 完整的 。 在本文中, 我们调查问题在不同方面的复杂性。 首先, 我们证明问题对于三度和任意大色的平面双面图类来说, 问题仍然是 NP 。 另外, 问题仍然是对以四度为最高层的平面平面图类的 NP 问题。 此外, 我们研究问题的参数复杂性。 特别是, 问题在于参数 k 1 的双面图形是W [1]- 硬的。 另一方面, 问题在于参数相对于参数 tw (k, c4) 和 c4 平面的平面图的平面的周期数数, 也证明了每个平面图的平面图。
相关内容
微信扫码咨询专知VIP会员