Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that pair of edges contained in a minimum weight (almost) perfect matching?
how is the situation for euclidean graphs, i.e. when the vertices correspond to points in euclidean space and the edge weights correspond to the distance between the points of the adjacent vertices?
I am interested in results about exact algorithms as well as about good heuristics.
Pointers to articles are also welcome.
