0
$\begingroup$

Given a weighted digraph $G$, and collections of vertices $R, S \subset V$ , consider the problem of finding a shortest length path joining a vertex $r\in R$ to a vertex $s\in S$. Reduce this to the shortest path problem from a given vertex to all other vertices.

I have been looking at this question for a while and I'm struggling to articulate what I am thinking. Clearly I should start by taking some fixed $a\in R$ and finding all the shortest paths from a to every other vertex, but I am unsure how to create the paths from any other $r\in R \setminus a$ to $s\in S$ since I cannot guarantee they are the shortest.

$\endgroup$
7
  • 1
    $\begingroup$ Do you need a many-one reduction or just a Turing reduction? $\endgroup$
    – Karl
    May 24 at 14:53
  • $\begingroup$ @Karl I think I am just supposed to reword the problem as I haven't encountered either reduction in this course. $\endgroup$
    – Maths Owl
    May 24 at 14:59
  • $\begingroup$ Or maybe a polynomial time reduction? Can you make multiple calls to the shortest paths subroutine? I'd review your notes to make sure. $\endgroup$
    – Karl
    May 24 at 14:59
  • $\begingroup$ @Karl Polynomial Time is the only reduction we have covered but even then very briefly. Maybe that's why I'm struggling? The whole question is written above so I assume anything goes. $\endgroup$
    – Maths Owl
    May 24 at 15:01
  • $\begingroup$ Yeah, "anything goes" isn't a well-defined task. If the problem says "reduce this", it should be clear what kind of reduction they're asking for. If it's a polynomial reduction, then (according to the Wikipedia definition) your solution can make multiple calls to the subroutine (e.g. one for every element of $R$). $\endgroup$
    – Karl
    May 24 at 15:06

1 Answer 1

Reset to default
1
$\begingroup$

Introduce a dummy "supersource" node $r_0$ and a directed arc with weight $0$ from $r_0$ to each $r\in R$. Now solve a shortest path problem from $r_0$ to all vertices. Let $d(r_0,i)$ be the resulting shortest-path distances. For the path that corresponds to $\min_{s\in S} d(r_0,s)$, the first arc indicates which $r\in R$ to use.

A similar idea with an additional dummy supersink node $s_0$ further reduces the problem to a single-source, single-sink shortest path problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .