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$ – David Eppstein Jan 10 '13 at 19:08
  • $\begingroup$ @DavidEppstein: yes, the weights satisfy the triangle inequality. Your idea looks interesting, thank you! $\endgroup$ – M.B. Jan 10 '13 at 19:54

(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 '13 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$ – Magnus Lie Hetland Jan 12 '13 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$ – Magnus Lie Hetland Jan 12 '13 at 1:25

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.