Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices What is the complexity of the following problem?

Input: 


$H$ a Hamiltonian path in $K_n$
$R \subseteq [n]^2$ a subset of pairs of vertices
a positive integer $k$


Query: is there a matching $M$ such that 
for every $(v,u) \in R$, $d_G(v,u) \leq k$?
(where $G = ([n], M\cup H)$)

I have been having a discussion with a friend about this problem. 
My friend thinks the problem is in polynomial time. 
I think it is NP-complete.
This answer is incorrect.

Your friend is right. Your problem (as interpreted by Sasho) does not place any restriction on the cardinality of the matching $C$. Therefore, choose $C$ to be a matching between the pairs in $R$. Then for any positive integer $k$, the distance between every pair in $R$ is less than $k$.

Your problem becomes interesting if you force paths to contain edges from both the matching $C$ and the path $P$.