Computation Theory
Exercise c. Strict matching
Consider the following generalization of the maximum matching problem, which we call
STRICT-MATCHING. Recall that a matching in an undirected graph G = (V, E) is a set
Copyright By PowCoder代写 加微信 powcoder
of edges such that no distinct pair of edges {a, b} and {c, d} have endpoints that are
equal: {a, b} n {c,d} = 0.
Say that a strict matching is matching with the property
that no pair of distinct edges have endpoints that are connected by an edge: {a, c & E.
fa, d7 & E, {b, c) & E, and {b, d) & E. (Since a strict matching is also a matching, we
also require fa.b}n{c.d=0. The problem STRICT-MATCHING is then given a graph
G and an integer k, does G contain a strict matching with at least k edges.
Prove that STRICT-MATCHING is NP-complete.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com