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 verticesa 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.
Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
cc.complexity theory;graph theory;graph algorithms;np hardness;np complete