Consider the problem “wellMath”, which is defined as follows:
{ Input: An undirected graph G = (V, E) and a positive integer p.
G contains a well-separated matching of size p. }
"We define a well-separated matching as a subset S ⊆ E such that no two edges in S share an endpoint, and for any distinct pair of edges x and y in S, each endpoint of x is at a distance of at least 2 (edges) from each endpoint of y in graph G"
Prove that the problem is NP complete.
I try to reduce INDSET to my problem by the following reduction : Giving a graph G and a number k, (<G, k> ) we add an edge to each vertices (with an other additional vertex to 2nd endpoint). I tried on many graph and it seems to work but im pretty convice that there is an counter example. What do you think about this reduction ?