Árvore de abrangência mínima em todas as correspondências de vértices

Corri para esse problema de correspondência para o qual não consigo escrever um algoritmo de tempo polinomial.

Seja gráficos completos ponderados com conjuntos de vértices e , respectivamente, onde . Além disso, sejam e as funções de peso nas arestas de e , respectivamente. $P, Q$ $P_V$ $Q_V$ $|P_V| = |Q_V|=n$ $w_P$ $w_Q$ $P$ $Q$

Para uma bijeção modificamos da seguinte forma: Se e com e defina . Indique esse gráfico modificado por e seja a soma dos pesos da árvore de abrangência mínima de . $f: P_V \to Q_V$ $Q$ $f(p) = q$ $f(p^\prime) = q^\prime$ $w_P(p, p^\prime) > w_Q(q, q^\prime)$ $w_Q(q, q^\prime) = w_P(p, p^\prime)$ $Q_f$ $W(Q_f)$ $Q_f$

Problema: Minimize $W(Q_f)$ em todas as $f: P_V \to Q_V$ .

Quão difícil é esse problema? Se "difícil": e os algoritmos de aproximação?

graph-theory optimization MB
fonte

Podemos assumir que os pesos em P e Q satisfazem separadamente a desigualdade do triângulo? Como, em caso afirmativo, encontrar um MST em cada um deles separadamente, formar um tour de Euler para transformá-lo em um caminho aproximado de vendedor ambulante e escolher uma correspondência que corresponda aos vértices nas posições de caminho correspondentes parece ser uma aproximação 2 para o seu problema .

David Eppstein

@ DavidEppstein: sim, os pesos satisfazem a desigualdade do triângulo. Sua ideia parece interessante, obrigado!

Respostas:

(Movido dos comentários) Aqui está uma idéia para obter uma aproximação constante de fatores, assumindo que P e Q satisfazem a desigualdade do triângulo. Eu pensei que poderia dar uma aproximação de 2, mas tudo o que posso provar agora é uma razão de aproximação de 4.

$pq$ $p$ $p'$ $q$ $q'$ $\max\{P(pq),Q(p'q')\}$ $P(pq)+Q(p'q')$ $P$ $Q$ $P$ $Q$

(2) Em , encontre uma árvore de abrangência mínima e use a técnica de tour de Euler com duplicação de caminho para encontrar um caminho com no máximo o dobro do peso. Faça a mesma coisa de forma independente em . O resultado são duas árvores isomórficas (ambos os caminhos) que são separadas, no máximo, duas vezes o peso dos MSTs de seus gráficos e, portanto, no máximo duas vezes o custo da solução para o problema mínimo de extensão de árvore isomórfica e quatro vezes o peso do problema original . $P$ $Q$

(3) O problema original é NP-completo, por uma redução do caminho hamiltoniano. Seja definido a partir de um gráfico no qual você deseja testar a existência de um caminho hamiltoniano; defina quando é uma aresta em e quando não é uma aresta. Seja definido exatamente da mesma maneira a partir de um gráfico de caminho. Existe uma solução de custo total se e somente se o gráfico a partir do qual foi definido tiver um caminho hamiltoniano. Provavelmente, isso também pode ser usado para provar a falta de aproximação abaixo de alguma constante fixa. $P$ $P(pq)=1$ $pq$ $P$ $2$ $pq$ $Q$ $n-1$ $P$

David Eppstein
fonte

Obrigado, esta é uma excelente resposta. (Aparentemente, eu não sou elegível para conceder-lhe a recompensa nas próximas 18 horas.)

Que tal usar a -approximation para a - Path TSP (experimente cada e ) para obter as duas árvores (ou seja, caminhos)? Arxiv.org/abs/1110.4604

(1 + \sqrt{5}) / 2

$(1+\sqrt{5})/2$

s

$s$

t

$t$

s

$s$

p

$p$

Magnus Lie Hetland

Pensando bem, isso só daria uma proporção para o caminho ideal, é claro, não para o MST. Então ... deixa pra lá;)

Magnus Lie Hetland