5
$\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$
1
  • 3
    $\begingroup$ What have you tried? Since there is no runtime restriction, this task should be trivial. $\endgroup$
    – Raphael
    Mar 26, 2013 at 11:15

3 Answers 3

5
$\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$
2
  • $\begingroup$ Shouldn't the first $\Theta$ be $\Theta(k(n+m))$? $\endgroup$
    – frafl
    Mar 26, 2013 at 11:56
  • $\begingroup$ @frafl Absolutely. I assumed $k$ to be constant for some reason. $\endgroup$
    – Raphael
    Mar 26, 2013 at 11:57
5
$\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$
8
  • $\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, 2013 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, 2013 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$ Mar 29, 2013 at 19:04
  • $\begingroup$ No more comments, add this to the and several stuff to the answer! $\endgroup$
    – frafl
    Mar 29, 2013 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$ Mar 30, 2013 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 and acknowledge you have read our privacy policy.

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