4
$\begingroup$

I need help with the following problem:

Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.

Question: Find a vertex $v$ of $V$ such that the distance from each vertex of $F$ to $v$ is the same and all the distances are minimized? Return None if there is no such $v$.

The runtime should be $O(|V| + |E|)$.

My thoughts were to do a breadth-first search for each vertex in $F$, so for each vertex in $F$, you store all vertices with their distances, then find the intersection of all these.

Is there a better way?

$\endgroup$
  • 3
    $\begingroup$ What have you tried? Since there is no runtime restriction, this task should be trivial. $\endgroup$ – Raphael Mar 26 '13 at 11:15
4
$\begingroup$

Assume $n = |V|, m = |E|, k = |F|$. Solve the SSSP for all $v \in F$ and annotate nodes with the respective distances (time $\Theta(k(n + m))$). Iterate over all nodes and find one all annotations of which are the same and minimal among all candidates (time $\Theta(nk)$).

This can be sped up by using depth-first search to solve the SSSP and executing all $k$ runs in parallel and in phases (by distance), observing the following rules.

  • In any given phase, if we find a node in some runs but not in others, remove them from consideration.
  • In any given phase, if a node is found in all runs (simultaneously), return it and stop.

Now the runtime depends on the minimal distance to be found and the density of the graph.

$\endgroup$
  • $\begingroup$ Shouldn't the first $\Theta$ be $\Theta(k(n+m))$? $\endgroup$ – frafl Mar 26 '13 at 11:56
  • $\begingroup$ @frafl Absolutely. I assumed $k$ to be constant for some reason. $\endgroup$ – Raphael Mar 26 '13 at 11:57
4
$\begingroup$

Starting with $i=0$ and going up, for every $f \in F$ consider a subset of $V$ containing points at the exact distance of $i$ from $f$. Look at intersection of all of those subsets. If you're lucky, as $i$ grows, you'll find this intersection non empty - those will be the solutions.

For the actual implementation, I'd suggest removing vertices closer than $i$ to any of $f$ at every iteration. To find intersection you could simply increment a counter on a vertex, whenever it is included in one of the subsets. When for some vertex v.count = |F|, you are done.

One way to implement it could be as follows

For each v in V, v.count = 0.

For each f in F,
    f.subset = {f},
    f.count = f.count + 1
    if f.count = |F|, return f.

While V is not empty,
    For each f in F, 
        old_subset = f.subset,
        f.subset = the set of neighbors of vertices in old_subset,
                   (consider only vertices in V and not in old_subset)

        For each v in old_subset, 
            if v.count == 1, remove v from V,
            else v.count = v.count - 1

        For each s in f.subset,
            s.count = s.count + 1
            if s.count = |F|, return s.

return "no such vertex"

While the running time of the above algorithm depends a lot on chosen graph representation, it can be as good as $O(|V| + |E|)$ assuming that you can find the neighbors of a vertex $v$ and remove it from the graph in $O(\deg(v))$ time. In that case, because $\sum_{v \in V} \deg(v) = 2 |E|$, most of the cost of the algorithm is covered by the $|E|$ term.

$\endgroup$
  • $\begingroup$ Regarding runtime: consider the complete bipartite graph $K_{k,n}$ and select as $F$ the $k$ nodes on one side. In this case, we clearly have $\Theta(kn)$ effort in the first (and only) iteration. Of course, $|E|=kn$ in this case; if we add all edges among the $n$ nodes, we are in $o(|E|)$, but I think $O(|E|)$ is an upper bound in any case. Convinced! @frafl I think we have given the same answer in multiple forms. ;) $\endgroup$ – Raphael Mar 28 '13 at 10:03
  • $\begingroup$ Suppose there are many equidistant nodes, how does this get the shortest one? (i.e. the distance from that node to any node in F is minimized) $\endgroup$ – omega Mar 29 '13 at 17:58
  • $\begingroup$ @omega, the algorithm considers sets $V_{f, i}$ of all vertices at distance $i$ from $f$. First $\cap_{f \in F}V_{f, 0}$ is checked. If there is no solution at distance $0$, then $\cap_{f \in F}V_{f, 1}$ is checked and etc. No vertices are ever skipped, none are ever removed before checking them. There is nothing that could make a farther solution pop up before a nearer one does. $\endgroup$ – Karolis Juodelė Mar 29 '13 at 19:04
  • $\begingroup$ No more comments, add this to the and several stuff to the answer! $\endgroup$ – frafl Mar 29 '13 at 19:30
  • 1
    $\begingroup$ @omega, Raphael, I now see that my implementation in indeed not $O(|V| + |E|)$. Consider a tree as this, but with a longer path between $4$ and $5$. It is counterexample with $F = {1, 2, 3, 6}$. Because node $4$ belongs in the subsets of each of nodes $1$, $2$, $3$, it, along with half of the nodes between $4$ and $5$, will be processed $3$ times. This should be solvable. I'll think about it... $\endgroup$ – Karolis Juodelė Mar 30 '13 at 7:49
2
$\begingroup$

One easy but most likely not most efficient approach is this:

  1. Reorder the vertices such that all vertices in $F$ come first.
  2. Use the Floyd-Warshall algorithm to compute the Matrix $M$ of all distances.
  3. Look at all columns where the first $|F|$ entries contain the same value $k$ and choose the one with the minimal $k$.

The worst case runtime is in $\mathcal{O}(|V|^3)$, since it's dominated by the Floyd-Warschall algorithm.


Another algorithm:

  1. Let $M$ be the adjacency matrix of $G$ (again with the vertices in $F$ first)
  2. If $F=\{v\}$ return $v$, if $F=\emptyset$ return an arbitrary $v \in V$, now $|F|>1$, so we know $v \notin F$.
  3. Compute $M^i=MM^{i-1}$ and flag every $v \in V\setminus F$ s.t. some but not all of the first $F$ rows are nonzero (i.e. there is a path of length $i$). Such a vertex can't be $v$ since at least 2 distances differ.
  4. Stop if you found a non flagged vertex $v$ that has all entries in the first $|F|$ rows nonzero and return $v$ or if all vertices in $V\setminus F$ are flagged and return "no such $v$ exists".

Note that we don't need the actual $M^i$ so we can speed up the expensive matrix multiplication to some extent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.