<p><strong>This answer is incorrect</strong>.</p>

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

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

CC BY-SA 3.0
2017-04-04T17:10:06.823Z
What do you mean by “matching between the pairs in $R$”?
Emil Jeřábek
CC BY-SA 3.0
2017-04-04T17:19:48.533Z
@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
CC BY-SA 3.0
2017-04-04T17:46:26.430Z
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
CC BY-SA 3.0
2017-04-04T18:11:34.927Z
@EmilJeřábek Yes. Your point is valid. I will edit my answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-04T18:14:43.197Z
@pfim Can the shortest path be formed using only edges from $C$?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-04T18:17:40.867Z
I don't see how picking a perfect matching in $R$ enforces that the shortest paths between each pair of vertices in $R$ do not exceed $K$.

I think it is clear from my question that the shortest paths may use edges from $P$, and I don't see that a constraint forcing this is necessary. (EDIT: Just saw your comment. The answer is no, shortest paths can use edges from $P$.)
pfim
CC BY-SA 3.0
2017-04-04T18:23:13.773Z
I've clarified this issue in my question. Thanks for finding this ambiguity!
pfim
CC BY-SA 3.0
2017-04-04T15:24:10.007Z
2017-04-04T18:17:58.133Z
2017-04-04T18:17:58.133Z
Mohammad Al-Turkistany
<p><strong>UPDATE:</strong> 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.</p>

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

<p>For every variable $x_i$ add a "variable gadget" with:</p>

<ul>
<li>three nodes $X_i, +X_i, -X_i$</li>
<li>two variable edges $(X_i,+X_i)$ and $(X_i,-X_i)$</li>
</ul>

<p>Add a source node $S$ and connect it to all variables $X_i$.</p>

<p>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.</p>

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

<p><a href="https://i.sstatic.net/7B4rl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7B4rl.png" alt="enter image description here"></a></p>

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

<p>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$).</p>

<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.</p>

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

<p>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:</p>

<p><a href="https://i.sstatic.net/iYptV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/iYptV.png" alt="enter image description here"></a></p>

<p>The original graph becomes:</p>

<p><a href="https://i.sstatic.net/UqkVM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/UqkVM.png" alt="enter image description here"></a></p>

<p>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$).</p>

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

<p>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:</p>

<p><a href="https://i.sstatic.net/viT49.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/viT49.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-04-06T19:26:14.503Z
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
CC BY-SA 3.0
2017-04-06T20:26:57.433Z
Ok, thank you ... I completely forgot what is a simple path :-( ... now it should be fixed.
Marzio De Biasi
CC BY-SA 3.0
2017-04-06T21:19:55.993Z
This post on math.SE  suggests that the problem may not be NP-complete. It could be intractable but solvable in quasipolynomial time http://math.stackexchange.com/questions/2218929/path-augmentation-to-minimize-the-diameter
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-06T21:27:24.847Z
@MohammadAl-Turkistany: do you see a flaw in the current version of the answer?
Marzio De Biasi
CC BY-SA 3.0
2017-04-06T21:30:13.243Z
No, I don't see any obvious flaw.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-07T01:34:49.013Z
I see a pretty big issue: there's not actually anything causing the clauses to connect to the variables you want. When augmenting the path with a matching, the clauses can connect to literals that are not even in the clause just as much as it can connect to literals in the clause..
Mikhail Rudoy
CC BY-SA 3.0
2017-04-07T06:52:30.320Z
The node $S$ must be connected to all $C_j$ (because we include the pairs in $R$) with a path not longer than $K$ (that must be adjusted according to the sum of the depths of the trees used to split the blue edges, K=11 in the example). If for a variable there is no need to add the edge $(X_i,+X_i)$ or $(X_i,-X_i)$, then all clauses are satisfied whatever truth value we assign to it. What matters here is the existence of a short path from $S$ to all $C_j$s, and the $\leq K$ path condition doesn't allow to use a clause $C_j$ as a "bridge" to connect $S$ to another clause $C_j'$
Marzio De Biasi
CC BY-SA 3.0
2017-04-07T07:59:16.310Z
I think Mikhail's objection is that in the penultimate figure, where $S$ connects directly to two nodes from its tree, nothing prevents the matching from linking each of those nodes directly to a $C_j$ for a path of length 2. In fact, in the original graph nothing stops the matching from connecting $S$ directly to a $C_j$ which can't be satisfied.
Peter Taylor
CC BY-SA 3.0
2017-04-07T10:48:05.947Z
@PeterTaylor: perhaps I don't understand the objection; what do you mean with "... where S connects directly to two nodes from its tree..."? In the original question, the picked edges of the matching must belong to the original edge set E of the graph ("*... if there is some subset of edges C you can chose from E ...*"). I think that Kaveh reformulation is not correct: the Hamiltonian path is not from $K_n$ but from an arbitrary graph $G$.
Marzio De Biasi
CC BY-SA 3.0
2017-04-07T10:52:57.870Z
The reformulation is correct: the original question said "*Suppose you have a complete graph $G=(V,E)$...*".
Peter Taylor
CC BY-SA 3.0
2017-04-07T10:57:06.220Z
@PeterTaylor: :-( you're right! I leave the answer and see if it can be fixed, or give some hints for another answer.
Marzio De Biasi
CC BY-SA 3.0
2017-04-06T18:42:48.653Z
2017-04-07T10:58:44.100Z
2017-04-07T10:58:44.100Z
Marzio De Biasi
<p>What is the complexity of the following problem?</p>

<p><strong>Input</strong>: </p>

<ul>
<li>$H$ a <a href="https://en.wikipedia.org/wiki/Hamiltonian_path" rel="noreferrer">Hamiltonian path</a> in <a href="https://en.wikipedia.org/wiki/Complete_graph" rel="noreferrer">$K_n$</a></li>
<li>$R \subseteq [n]^2$ a subset of pairs of vertices</li>
<li>a positive integer $k$</li>
</ul>

<p><strong>Query</strong>: is there a <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)" rel="noreferrer">matching</a> $M$ such that 
for every $(v,u) \in R$, $d_G(v,u) \leq k$?<br>
(where $G = ([n], M\cup H)$)</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-25T22:25:30.783Z
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
CC BY-SA 3.0
2017-04-04T18:23:36.987Z
I think this formulation may be confusing after my latest edit to remove some ambiguity.
pfim
CC BY-SA 3.0
2017-04-05T00:50:31.260Z
My interpretation is correct, isn't it?
Sasho Nikolov
CC BY-SA 3.0
2017-04-07T00:20:18.623Z
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
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness><np-complete>
Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
pfim
# Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

(Asked by: username_0 on 2017-03-25)

What is the complexity of the following problem?

**Input**:

* $H$ a [Hamiltonian path](https://en.wikipedia.org/wiki/Hamiltonian_path) in [$K\_n$](https://en.wikipedia.org/wiki/Complete_graph)
* $R \subseteq [n]^2$ a subset of pairs of vertices
* a positive integer $k$

**Query**: is there a [matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)) $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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness, np-complete

> **Comments:**
> **username_1**: 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$.  
> **username_0**: I think this formulation may be confusing after my latest edit to remove some ambiguity.  
> **username_1**: My interpretation is correct, isn't it?  
> **username_2**: 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$.  

---

## 2 answers

### Answer by username_3 on 2017-04-04. Score: 1

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

> **Comments:**
> **username_4**: What do you mean by “matching between the pairs in $R$”?  
> **username_3**: @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$.  
> **username_4**: 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$?  
> **username_3**: @EmilJeřábek Yes. Your point is valid. I will edit my answer.  
> **username_3**: @username_0 Can the shortest path be formed using only edges from $C$?  
> **username_0**: I don't see how picking a perfect matching in $R$ enforces that the shortest paths between each pair of vertices in $R$ do not exceed $K$.  I think it is clear from my question that the shortest paths may use edges from $P$, and I don't see that a constraint forcing this is necessary. (EDIT: Just saw your comment. The answer is no, shortest paths can use edges from $P$.)  
> **username_0**: I've clarified this issue in my question. Thanks for finding this ambiguity!  

---

### Answer by username_5 on 2017-04-06. Score: 0

**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)$

[![enter image description here](https://i.sstatic.net/7B4rl.png)](https://i.sstatic.net/7B4rl.png)

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:

[![enter image description here](https://i.sstatic.net/iYptV.png)](https://i.sstatic.net/iYptV.png)

The original graph becomes:

[![enter image description here](https://i.sstatic.net/UqkVM.png)](https://i.sstatic.net/UqkVM.png)

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:

[![enter image description here](https://i.sstatic.net/viT49.png)](https://i.sstatic.net/viT49.png)

> **Comments:**
> **username_6**: 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.  
> **username_5**: Ok, thank you ... I completely forgot what is a simple path :-( ... now it should be fixed.  
> **username_3**: This post on math.SE  suggests that the problem may not be NP-complete. It could be intractable but solvable in quasipolynomial time http://math.stackexchange.com/questions/2218929/path-augmentation-to-minimize-the-diameter  
> **username_5**: @MohammadAl-Turkistany: do you see a flaw in the current version of the answer?  
> **username_3**: No, I don't see any obvious flaw.  
> **username_6**: I see a pretty big issue: there's not actually anything causing the clauses to connect to the variables you want. When augmenting the path with a matching, the clauses can connect to literals that are not even in the clause just as much as it can connect to literals in the clause..  
> **username_5**: The node $S$ must be connected to all $C_j$ (because we include the pairs in $R$) with a path not longer than $K$ (that must be adjusted according to the sum of the depths of the trees used to split the blue edges, K=11 in the example). If for a variable there is no need to add the edge $(X_i,+X_i)$ or $(X_i,-X_i)$, then all clauses are satisfied whatever truth value we assign to it. What matters here is the existence of a short path from $S$ to all $C_j$s, and the $\leq K$ path condition doesn't allow to use a clause $C_j$ as a "bridge" to connect $S$ to another clause $C_j'$  
> **username_7**: I think Mikhail's objection is that in the penultimate figure, where $S$ connects directly to two nodes from its tree, nothing prevents the matching from linking each of those nodes directly to a $C_j$ for a path of length 2. In fact, in the original graph nothing stops the matching from connecting $S$ directly to a $C_j$ which can't be satisfied.  
> **username_5**: @PeterTaylor: perhaps I don't understand the objection; what do you mean with "... where S connects directly to two nodes from its tree..."? In the original question, the picked edges of the matching must belong to the original edge set E of the graph ("*... if there is some subset of edges C you can chose from E ...*"). I think that username_2 reformulation is not correct: the Hamiltonian path is not from $K_n$ but from an arbitrary graph $G$.  
> **username_7**: The reformulation is correct: the original question said "*Suppose you have a complete graph $G=(V,E)$...*".  
> **username_5**: @PeterTaylor: :-( you're right! I leave the answer and see if it can be fixed, or give some hints for another answer.  

---

