# 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.

• You can simplify this further, at least in terms of presentation. You are given $k$, a path with $n$ vertices, and a collection $R$ of pairs of these vertices. You want to augment the path with a matching so that the distance between any pair in $R$ is at most $k$. – Sasho Nikolov Mar 25 '17 at 22:25
• I think this formulation may be confusing after my latest edit to remove some ambiguity. – pfim Apr 4 '17 at 18:23
• My interpretation is correct, isn't it? – Sasho Nikolov Apr 5 '17 at 0:50
• I did an edit to make the problem statement more rigorous. I think this can be further simplified because as you can simply assume that H is the Hamiltonian path 1-2-3-4-5...-n without loss of generality. So you just need $n$. – Kaveh Apr 7 '17 at 0:20

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$.

• What do you mean by “matching between the pairs in $R$”? – Emil Jeřábek Apr 4 '17 at 17:10
• @EmilJeřábek It means connecting the nodes of every pair in $R$ by an edge. So $C$ is just $R$ with an edge connecting every pair. This is equivalent to augmenting the path $P$ with a perfect marching on the pairs of $R$. – Mohammad Al-Turkistany Apr 4 '17 at 17:19
• That does not seem to make much sense to me. What if $R$ is not a matching? Say, if $R$ contains the pairs $(1,2)$ and $(1,3)$, how do you choose $C$? – Emil Jeřábek Apr 4 '17 at 17:46
• @EmilJeřábek Yes. Your point is valid. I will edit my answer. – Mohammad Al-Turkistany Apr 4 '17 at 18:11
• @pfim Can the shortest path be formed using only edges from $C$? – Mohammad Al-Turkistany Apr 4 '17 at 18:14

UPDATE: the answer below is not correct, because I wrongly assumed that the Hamiltonian path is in an arbitrary graph, not in $K_n$. I leave it undeleted, perhaps I'll be able to fix it or it will give some hints for another answer.

I think it's NP-complete. This is a very informal/quick reduction idea from 3SAT

For every variable $x_i$ add a "variable gadget" with:

• three nodes $X_i, +X_i, -X_i$
• two variable edges $(X_i,+X_i)$ and $(X_i,-X_i)$

Add a source node $S$ and connect it to all variables $X_i$.

For each clause $C_j$ add a node $C_j$ and connect it to the corresponding variables $+X_i$ or $-X_i$ that forms the clause.

The following picture represents: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

The set $R$ (nodes that must be linked) contains $(S, C_1), (S,C_2), ...$

The simple path $P$ should include all "BLUE" edges except the variable edges $(X_i, +X_i)$ and $(X_i, -X_i)$ (in the picture above the blue edges represent the edges that we include in $P$).

At this point, the initial formula is satisfiable if and only if the shortest path from $S$ to each clause node $C_j$ is not greater than three. Indeed to reach a clause from $S$ in three steps we must traverse at least one variable $X_i$: $S \to X_i \to \pm X_i \to C_j$. So we must traverse one of the two edges: $X_i \to +X_i$ or $X_i \to -X_i)$ and include it into $C$ (because by construction it's not part of $P$). But both cannot be included, because they share a vertex.

But we're not sure that we can build a simple path $P$ that includes all the blue edges because some nodes have more than one incident blue edge.

To fix this we replace each node with multiple incident blue edges, with a tree that contains only pairs of incident blue edges that will be included in $P$ and edges that separate them and that should be included in $C$ to reach the clause nodes:

The original graph becomes:

Each tree should have the same depth (we just can pick the max of the depth required for all the clauses/variables/S); and we must increase the value of $K$ accordingly (the number of steps to reach $C_j$ from $S$).

We can include in $C$ all the needed (not blue) edges required to reach the clause nodes because they share no vertex.

Furthermore with this construction we are able to build a simple path $P$ that traverse each vertex and each blue edge, just add extra nodes to avoid shortcuts between the clauses or variables:

• Trying to build a path that contains all the blue edges worries me: some vertices have more than 2 blue edges incident on them, so there can't be any single simple path including all the blue edges. – Mikhail Rudoy Apr 6 '17 at 19:26
• Ok, thank you ... I completely forgot what is a simple path :-( ... now it should be fixed. – Marzio De Biasi Apr 6 '17 at 20:26
• This post on math.SE suggests that the problem may not be NP-complete. It could be intractable but solvable in quasipolynomial time math.stackexchange.com/questions/2218929/… – Mohammad Al-Turkistany Apr 6 '17 at 21:19
• @MohammadAl-Turkistany: do you see a flaw in the current version of the answer? – Marzio De Biasi Apr 6 '17 at 21:27
• No, I don't see any obvious flaw. – Mohammad Al-Turkistany Apr 6 '17 at 21:30