What is the complexity of the following problem?


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

  • 11
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Mar 25 '17 at 22:25
  • $\begingroup$ I think this formulation may be confusing after my latest edit to remove some ambiguity. $\endgroup$ – pfim Apr 4 '17 at 18:23
  • 1
    $\begingroup$ My interpretation is correct, isn't it? $\endgroup$ – Sasho Nikolov Apr 5 '17 at 0:50
  • $\begingroup$ 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$. $\endgroup$ – Kaveh Apr 7 '17 at 0:20

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

  • $\begingroup$ What do you mean by “matching between the pairs in $R$”? $\endgroup$ – Emil Jeřábek Apr 4 '17 at 17:10
  • $\begingroup$ @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$. $\endgroup$ – Mohammad Al-Turkistany Apr 4 '17 at 17:19
  • 1
    $\begingroup$ 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$? $\endgroup$ – Emil Jeřábek Apr 4 '17 at 17:46
  • $\begingroup$ @EmilJeřábek Yes. Your point is valid. I will edit my answer. $\endgroup$ – Mohammad Al-Turkistany Apr 4 '17 at 18:11
  • $\begingroup$ @pfim Can the shortest path be formed using only edges from $C$? $\endgroup$ – 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)$

enter image description here

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

The original graph becomes:

enter image description here

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

  • $\begingroup$ 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. $\endgroup$ – Mikhail Rudoy Apr 6 '17 at 19:26
  • $\begingroup$ Ok, thank you ... I completely forgot what is a simple path :-( ... now it should be fixed. $\endgroup$ – Marzio De Biasi Apr 6 '17 at 20:26
  • $\begingroup$ 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/… $\endgroup$ – Mohammad Al-Turkistany Apr 6 '17 at 21:19
  • $\begingroup$ @MohammadAl-Turkistany: do you see a flaw in the current version of the answer? $\endgroup$ – Marzio De Biasi Apr 6 '17 at 21:27
  • $\begingroup$ No, I don't see any obvious flaw. $\endgroup$ – Mohammad Al-Turkistany Apr 6 '17 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.