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
- Recommended textbooks for youDatabase System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSONDatabase System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSONC How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag…Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education