Shortest Path along an MST
David Eppstein
> INSTANCE: A point set in the plane, a positive real value $r$.
>
> QUESTION: given a pair of points $p$ and $q$, is there a path from
> $p$ to $q$ along an EMST(Euclidean MST), such that
> its length is not greater than $r$?
The graph version of this problem is NP-complete by a reduction from 3SAT.
I haven't worked out the details of the geometric version but my guess is
that it's also NP-complete by a similar reduction.
Details:
We will make a graph with two lengths of edges, "long" and "short", with
subgraphs ("gadgets") corresponding to each variable and clause of a
given 3SAT problem. The shortest path in this graph will go through the
gadgets one at a time in order (the particular order is not important)
and will consist of (a polynomial number of) only long edges. If the
3SAT problem is satisfiable, then there is a shortest path that is part
of some MST. The short edges will be grouped into chains (of a larger
polynomial number of edges) so that no detour through short edges can
shorten the overall path. Note that in an MST, it is impossible to have
a path of long edges that includes both endpoints of such a chain.
The gadget for a variable looks like the following, where each vertical
bar represents a chain of short edges and the remaining dashes and
slashes represent single long edges:
| | | |
o - o - o - o
/ \
o o
\ /
o - o - o - o
| | | |
The path enters on the left and exits on the right.
Note that it can go on the upper chain (corresponding to assignments
in which the variable is true) or the lower chain (corresponding to
assignments in which the variable is false) but not both.
The "dangling" chains of short edges will connect to clause gadgets.
There can be any number of dangling chains as long as the upper number
matches the lower number (in my drawing there are four on each side).
The gadget for a clause looks like the following (with same conventions):
|
o
/ \
/ \
/ | \
o - o - o
\ /
\ /
\ /
o
|
If a clause has the positive form of a variable, the corresponding
short chain connects to a vertex on the lower chain of the variable's gadget,
and if a clause has the negative form of a variable, the
corresponding short chain connects to a vertex on the upper chain of the
variable's gadget. Any shortest path must use exactly one of the three
routes through the clause gadget, and the shortest path can only be part
of an MST if the other end of the short chain is not also on the path.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Dae Y. Seo
I'd like to know if there is an polynomial algorithm for the following
problem:
INSTANCE: A point set in the plane, a positive real value $r$.
QUESTION: given a pair of points $p$ and $q$, is there a path from
$p$ to $q$ along an EMST(Euclidean MST), such that
its length is not greater than $r$?
Is this problem solvable in polynomial or NP-hard?
Any comment is welcome.
Thank you.
Dae Y. Seo
--
/ Dae Y. Seo | Email: se...@ece.nwu.edu \
/ 2145 Sheridan Rd |
/ Department of ECE | \
/ Northwestern University | \
Nick Maclaren
David Eppstein <epps...@ics.uci.edu> wrote:
>Dae Y. Seo writes:
> > INSTANCE: A point set in the plane, a positive real value $r$.
> >
> > QUESTION: given a pair of points $p$ and $q$, is there a path from
> > $p$ to $q$ along an EMST(Euclidean MST), such that
> > its length is not greater than $r$?
>
>I haven't worked out the details of the geometric version but my guess is
>that it's also NP-complete by a similar reduction.
Aargh! You mean THAT meaning of MST! My previous posting is then
completely wrong, because it was addressing a different problem.
However, this does show that two apparently identical formulations
may have entirely different complexities :-)
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Nick Maclaren
In article <7ere0d$djj$1...@news.ece.nwu.edu>, se...@cad2.ece.nwu.edu (Dae Y. Seo) writes:
|> Hi folks,
|>
|> I'd like to know if there is an polynomial algorithm for the following
|> problem:
|>
|>
|> QUESTION: given a pair of points $p$ and $q$, is there a path from
|> $p$ to $q$ along an EMST(Euclidean MST), such that
|> its length is not greater than $r$?
|>
If I understand you correctly, it can be done in O(N^3 log N) time,
and probably faster.
You can produce a data structure that includes all minimum spanning
trees for N points in O(N^2) time. You can then work out the
minimum distances between all pairs of points using that ultrametric
as your new distance function in O(N^3 log N) time or better, unless
my memory is playing me tricks. And Bob's your uncle!
What is more, this will work for any distance function, not just a
Euclidean one.
Jon Haugsand
> Aargh! You mean THAT meaning of MST! My previous posting is then
> completely wrong, because it was addressing a different problem.
This begs the question of a novice: What _is_ an MST?
--
Jon Haugsand
Norwegian Computing Center, <http://www.nr.no/engelsk/>
<mailto:haug...@nr.no> Pho: +47 22852608 / +47 22852500,
Fax: +47 22697660, Pb 114 Blindern, N-0314 OSLO, Norway
Nick Maclaren
Jon Haugsand <haug...@procyon.nr.no> wrote:
>* Nick Maclaren
>> Aargh! You mean THAT meaning of MST! My previous posting is then
>> completely wrong, because it was addressing a different problem.
>
>This begs the question of a novice: What _is_ an MST?
Minimum Spanning Tree. The confusion arises in the meaning of the
word "minimum", especially as much of the early work on them was
done in the taxonomy area where the basic models are often subtly
different from the graph theoretic area. And, in particular,
whether distances are summed using addition or taking the maximum.
In case the words aren't clear, it is a tree (i.e. a set of links,
without loops, that connects all points.) And it is minimal, in
some suitable sense. I believe that the usual graph theoretic one
is the sum of the lengths of all the links - which is not the most
useful definition for most forms of taxonomy.
And, as you have seen, the PRECISE definition can make the difference
between computationally trivial and intractable problems.
David Eppstein
If there are lots of equal length edges, there may be exponentially
many different MSTs. The original question was on the complexity
of finding the shortest path that is contained in some MST,
among points in the Euclidean plane. (Obviously the problem
is trivial when there are no equal edge lengths and only one MST.)
In a previous message, I showed that the general graph version of the
problem is NP-complete, by a reduction from 3SAT. But, in the Euclidean
problem, one can find a planar graph that contains all possible MST edges,
so my previous reduction can't be made Euclidean.
I now have a different reduction, from planar 3-colorability,
which shows that the planar graph version is NP-complete.
I think the Euclidean case is then just a matter of laying out the
resulting planar graph nicely. (In my previous message, I said
that the Euclidean case should be NP-complete, but of course it should
just be NP-hard since we don't know how to compare sums of Euclidean
distances in NP.)
Here's a (very informal) outline of the reduction.
As before, I'll use a graph with two edge lengths. The short edges will
be formed into chains of many edges, so that the desired shortest MST
path will be formed only of long edges. Say that a path is "good" if it
is formed of long edges and is contained in some MST. The reduction
will produce a problem in which the shortest MST path is good iff the
original graph is 3-colorable.
The new proof uses a special "crossover gadget":
|
o
|\
o \
/| \
-o-o-o-o-o-
\ |/
\ o
\|
o
|
In this drawing the vertical and horizontal edges are long and the
slashes and backslashes represent chains of short edges. The only good
paths are the ones going horizontally or vertically. It's impossible for
a good path to turn or to use both the horizontal and vertical parts.
Now, given a planar graph for which we want to test 3-coloring, I'll
form a different planar graph for which we want to test the existence of
a good path, in the following way. Assume the graph is embedded.
First, find a set of arcs forming a tour of all the vertices, with each
arc being strictly interior to a face (i.e. no arc can cross a vertex of
the original graph). I'll assume for now that the tour visits each
vertex once, but we can handle repeated vertices as described later.
Replace each vertex of the planar graph with a gadget like the
following:
---o=====o---
Here the ---o and o--- portions are incoming and outgoing arcs of the tour.
The o=====o portion represents a set of three different paths,
one labeled with each possible color the vertex may have.
These three paths may wiggle around and cross over each other
using the crossover gadget, e.g. here's an expanded view
(all dashes and slashes are long, the X's are crossovers):
____ ____
/ \ / \green
red/ \ / \
/ blue X blue \
---o----- / \ -----o---
\ \ / \ / /
green\ X X /red
\__/ \___/ \__/
blue
So (since the tour itself avoids the original graph's edges) there's
enough room to wiggle these colored paths along the edges of the
original graph until the green path passes near the green path of each
neighboring vertex (at which point we attach them by a chain of short
edges so that only one of the two paths can be taken), the red path
passes near the red path of each neighboring vertex, etc. We should be
careful doing this so that no path crosses itself, and no path crosses a
differently colored path of a neighboring vertex, but this is not difficult.
If the tour passes through a vertex k times, just use k of these gadgets,
where each one is responsible for handling some of the interactions with
neighboring vertices, and with similar interactions among these k gadgets that
force each one to use the same color path (e.g. the green path of one
gadget interacts with any red and blue paths of other gadgets -- it's
not hard to do this without needing to cross over any other green paths).