I ran into this matching problem for which I am unable to write down a polynomial time algorithm.

Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| = |Q_V|=n$. Also, let $w_P$ and $w_Q$ be the weight functions on the edges of $P$ and $Q$, respectively.

For a bijection $f: P_V \to Q_V$ we modify $Q$ in the following fashion: If $f(p) = q$ and $f(p^\prime) = q^\prime$ with $w_P(p, p^\prime) > w_Q(q, q^\prime)$ then set $w_Q(q, q^\prime) = w_P(p, p^\prime)$. Denote this modified graph by $Q_f$ and let $W(Q_f)$ be the sum of weights of the minimum spanning tree of $Q_f$.

Problem: Minimize $W(Q_f)$ over all bijections $f: P_V \to Q_V$.

How hard is this problem? If "hard": what about approximation algorithms?

  • $\begingroup$ Can we assume that the weights in P and Q separately satisfy the triangle inequality? Because if so then finding a MST in each of them separately, forming an Euler tour to turn it into an approximate traveling salesman path, and choosing a matching that matches vertices in corresponding path positions looks like it should be a 2-approximation to your problem. $\endgroup$ Jan 10, 2013 at 19:08
  • $\begingroup$ @DavidEppstein: yes, the weights satisfy the triangle inequality. Your idea looks interesting, thank you! $\endgroup$
    – M.B.
    Jan 10, 2013 at 19:54

1 Answer 1


(Moved from comments) Here's an idea for getting a constant factor approximation, assuming P and Q satisfy the triangle inequality. I thought it might give a 2-approximation, but all I can prove right now is an approximation ratio of 4.

(1) In the problem as stated, the weight of edge $pq$ in the combined graph (after the correspondence $p$–$p'$ and $q$–$q'$ is determined) is $\max\{P(pq),Q(p'q')\}$. Instead, let's use $P(pq)+Q(p'q')$. This loses at most a factor of two but makes the problem easier to describe: we are now trying to find a spanning tree in $P$, and an isomorphic spanning tree in $Q$, with minimum total weight. The correspondence between $P$ and $Q$ is then given by the isomorphism between these two trees.

(2) In $P$, find a minimum spanning tree, and use the path-doubling Euler tour technique to find a path with at most twice the weight. Do the same thing independently in $Q$. The result is two isomorphic trees (both paths) that are separately at most twice the weight of their graph's MSTs, and therefore at most twice the cost of the solution to the minimum isomorphic spanning tree problem, and four times the weight of the original problem.

(3) The original problem is NP-complete, by a reduction from Hamiltonian path. Let $P$ be defined from a graph in which you wish to test the existence of a Hamiltonian path; define $P(pq)=1$ when $pq$ is an edge in $P$ and $2$ when $pq$ is not an edge. Let $Q$ be defined in exactly the same way from a path graph. Then there is a solution of total cost $n-1$ if and only if the graph from which $P$ was defined has a Hamiltonian path. Probably this can also be used to prove inapproximability below some fixed constant.

  • $\begingroup$ Thank you, this is an excellent answer. (Apparently, I am not eligible to award you the bounty in the next 18 hours.) $\endgroup$
    – M.B.
    Jan 10, 2013 at 23:20
  • $\begingroup$ How about using the $(1+\sqrt{5})/2$-approximation for the $s$-$t$ Path TSP (try every $s$ and $p$) to get the two trees (i.e., paths)? arxiv.org/abs/1110.4604 $\endgroup$ Jan 12, 2013 at 1:15
  • $\begingroup$ On second thought, that'd only give you a ratio for the optimal path, of course, not the MST. So … nevermind ;) $\endgroup$ Jan 12, 2013 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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