3
$\begingroup$

In the graph below, N and M are most remote, and H is also an extremum.

An example graph

Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the subject? Does an algorithm exist for finding the most remote edges of a graph?

Please note that I am not asking you to invent an algorithm, but I'm asking for information.

$\endgroup$
5
  • 1
    $\begingroup$ "Has this problem been formalized?" What problem? $\endgroup$ Commented Sep 14, 2018 at 14:08
  • $\begingroup$ Please change "most remote edges" to "most remote vertices" in the title and in the body. Although there is a way to define "the most remote edges" to be subtly different from "the most remote vertices". However, I do not think that is your intention according to the given example. $\endgroup$
    – John L.
    Commented Sep 14, 2018 at 15:52
  • 1
    $\begingroup$ This sounds like the diameter of a graph, which is the maximum distance between two vertices. Finding the diameter of a graph is a well-known problem. $\endgroup$ Commented Sep 17, 2018 at 2:08
  • $\begingroup$ @YuvalFilmus The diameter will only point to H and M, but I also want to find N. $\endgroup$
    – MrMartin
    Commented Sep 17, 2018 at 6:37
  • $\begingroup$ @MrMartin. No, the diameter are $N$ and $M$, the distance between which is 9. There is no diameter that contains $H$. $\endgroup$
    – John L.
    Commented Sep 19, 2018 at 14:56

1 Answer 1

2
$\begingroup$

One way to formulate your problem is well known as finding the diameter of a graph as the following description in Wikipedia.

The diameter $d$ d of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively, $d=\max_{v\in V}\epsilon (v)$. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter. Formally, $v$ is peripheral if $\epsilon (v)=d$.

Similarly to the way we talk about the diameter of a circle, the term "diameter of a graph" is overloaded. It can also mean, although less frequently, any shortest path between any two vertices whose length is equal to the maximum eccentricity.

If the graph is a tree, there is an algorithm that finds its diameter using only two BFS scans. Choose an arbitrary vertex $v$. Do a breadth first search from $v$ that finds a vertex that is farthest away from $v$. Call the vertex $u$. Do another BFS from $u$ that finds a vertex that is farthest away from $u$. Call the vertex $u'$. The distance between $u$ and $u'$ is the diameter of the graph.

In a general graph, many algorithms can be used to to find the diameter of a graph. Please check this CS StackExchange question and answer, where most algorithms are in fact designed to solve the all-pairs-shortest-path problem.

In the example graph given in the question, the distance between $N$ and $M$, 9, is the diameter. In fact, $N$ and $M$ are the only two peripheral vertices in that graph. (OP calls peripheral vertices as most remote). However, $H$ is not a peripheral vertex, since the furthest distance from any vertex to $H$ is only 8. ($H$ is not a pseudo-peripheral vertex, either.)

We could define an extremum of a graph as a vertex whose eccentricity is not smaller than the eccentricity of any of its neighbors. We could also define a strong extremum of a graph as a vertex whose distance to any vertex $v$ is not smaller than the distance from any of its neighbors to $v$. Every peripheral vertices is an extremum and every strong extremum is an extremum. We can recall a leaf vertex of a graph means a vertex of degree 1. Every leaf is a strong extremum. Note that $H$ is a leaf. All those algorithms that compute all-pairs-shortest-paths can be adapted easily to find all (strong) extremum vertices as well. A simple degree-counting algorithm will find all leaves of a graph. (Please note this definition of "extremum" might not be standard at all. As far as I have tried, I have not found a single article that defines that concept. Well, I can only check probably a negligible number of articles among a myriad of them. There is probably some existing term for it in papers about social network.)

$\endgroup$
8
  • $\begingroup$ Right, the diameter will give me the pair of most remote edges from each other, but not all extrema. What if I'm also interested in finding H? $\endgroup$
    – MrMartin
    Commented Sep 17, 2018 at 6:40
  • $\begingroup$ You want to find all vertices of maximum eccentricity. $\endgroup$ Commented Sep 17, 2018 at 6:45
  • $\begingroup$ @YuvalFilmus, I am afraid that you have been misled by the example graph since $H$ does not have maximum eccentricity, although it looks like $H$ does. $\endgroup$
    – John L.
    Commented Sep 17, 2018 at 11:40
  • $\begingroup$ If the graph is a cycle, all nodes are on a diameter, but none of them is an extreme. Regarding degree-counting, if H were to connect to itself it would have higher degree than L or C. $\endgroup$
    – MrMartin
    Commented Sep 19, 2018 at 13:20
  • $\begingroup$ The biggest factor here is that you have not defined what is an "extremum" and there is no standard definition to that term. I have not found even one definition of that term applied to graph theory. So, per your request, I decided to settle down on one of my many choices. $\endgroup$
    – John L.
    Commented Sep 19, 2018 at 15:12

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.