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 of edges such that no distinct pair of edges {a, b} and {c, d} have endpoints that are equal: {a, b} ∩ {c, d} = ∅. 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, {a, d} ̸∈ E, {b, c} ̸∈ E, and {b, d} ̸∈ E.
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
of edges such that no distinct pair of edges {a, b} and {c, d} have endpoints that are
equal: {a, b} ∩ {c, d} = ∅. 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,
{a, d} ̸∈ E, {b, c} ̸∈ E, and {b, d} ̸∈ E. (Since a strict matching is also a matching, we
also require {a, b} ∩ {c, d} = ∅.) 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.
Answer:
The proof that Strict-Matching is NP-complete is shown through a reduction from the well-known NP-complete problem Maximum Independent Set (MIS), which is defined as follows: Given an undirected graph G = (V, E) and an integer k, does G contain an independent set with at least k nodes, where an independent set is a set of vertices such that no two vertices are connected by an edge.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
