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

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

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

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

CC BY-SA 3.0
2013-01-10T23:20:02.977Z
Thank you, this is an excellent answer. (Apparently, I am not eligible to award you the bounty in the next 18 hours.)
M.B.
CC BY-SA 3.0
2013-01-12T01:15:58.733Z
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)? http://arxiv.org/abs/1110.4604
Magnus Lie Hetland
CC BY-SA 3.0
2013-01-12T01:25:55.093Z
On second thought, that'd only give you a ratio for the optimal path, of course, not the MST. So … nevermind ;)
Magnus Lie Hetland
CC BY-SA 3.0
2013-01-10T21:26:05.117Z
2013-01-10T21:26:05.117Z
David Eppstein
<p>I ran into this matching problem for which I am unable to write down a polynomial time algorithm. </p>

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

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

<p><strong>Problem:</strong> Minimize $W(Q_f)$ over all bijections $f: P_V \to Q_V$. </p>

<p>How hard is this problem? If "hard": what about approximation algorithms?</p>

CC BY-SA 3.0
2013-01-10T19:08:37.777Z
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.
David Eppstein
CC BY-SA 3.0
2013-01-10T19:54:46.493Z
@DavidEppstein: yes, the weights satisfy the triangle inequality. Your idea looks interesting, thank you!
M.B.
<graph-theory><optimization>
Minimum spanning tree over all vertex matchings
M.B.
# Minimum spanning tree over all vertex matchings

(Asked by: username_0 on 2013-01-08)

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?

**Tags:** graph-theory, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: @DavidEppstein: yes, the weights satisfy the triangle inequality. Your idea looks interesting, thank you!  

---

## 1 answers

### Answer by username_1 on 2013-01-10. Score: 11 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you, this is an excellent answer. (Apparently, I am not eligible to award you the bounty in the next 18 hours.)  
> **username_2**: 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)? http://arxiv.org/abs/1110.4604  
> **username_2**: On second thought, that'd only give you a ratio for the optimal path, of course, not the MST. So … nevermind ;)  

---

