1
$\begingroup$

consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ distance of the $n$ vertices (measured in edge count of the shortest path). in a sense the $n$ vertices are "hubs" of the graph. (there may be other constraints on their selection.) suspect this problem may arise in a variety of guises. am not nec. looking for an exact solution.

looking for the contexts this arises (applications) & recent literature/survey(s) on this problem, finding the "natural" "hubs" of a graph.

possibly somewhat related is finding/adding a few edges to yield "good" hubs (hub sets that are small relative to the vertices they "reach").

Improve this question
$\endgroup$
6
  • 8
    $\begingroup$ seems equivalent to Dominating Set in the $d$-th power of the graph. Also search for "distance dominating set." $\endgroup$
    – Austin Buchanan
    Dec 24 '13 at 3:46
  • 1
    $\begingroup$ Sounds like you should be looking at finding interesting subgraphs in social networks. In social network analysis, a $k$-clique is a maximal set of vertices that are at a distance no greater than $d$ from each other. You might also be interested in $k$-clans and $k$-clubs. $\endgroup$
    – Juho
    Dec 24 '13 at 7:04
  • 1
    $\begingroup$ to add to Austin's comment: the optimization problem of minimizing $n$ given $d$ and the graph is equivalent to Min Set Cover under approximation preserving reductions. So you can approximate the smallest $n$ up to $\ln N$ and no better, where $N$ is the size of the graph. $\endgroup$
    – Sasho Nikolov
    Dec 24 '13 at 8:23
  • $\begingroup$ agreed with austins reformulation, thx. the problem does have ties to social network analysis, marketing or finding "influencers" and also viral spreading, and transportation networks. it is not exactly the same as finding cliques in the original graph although that is similar. it may be close to finding cliques in the $d$-th power of the graph. it seems to be closely tied to the "degrees of separation" concept, small world graphs etc $\endgroup$
    – vzn
    Dec 24 '13 at 16:33
  • $\begingroup$ taking austins tip, a std concept/approach in this area is eg $(k,r)$-domination in graphs & there are common applications in devising wireless and power network configurations/coverages $\endgroup$
    – vzn
    Dec 28 '13 at 18:32
6
$\begingroup$

When n is given and the objective is to minimize d, it is the well-known n-center problem.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ In particular, there's "simple" 2-approximation. Pick any vertex, pick the vertex furthest from it, pick the next one that has maximum distance from these two, and so on till you have $n$ centers. $\endgroup$
    – Suresh Venkat
    Dec 26 '13 at 1:24
  • $\begingroup$ apparently a subarea of the facility location problem also called "k-center" problem but which apparently in that case is not limited to graphs ie may use more general concepts of spatial distances/distance metrics. $\endgroup$
    – vzn
    Dec 28 '13 at 18:39
  • $\begingroup$ also metric k-center $\endgroup$
    – vzn
    Dec 28 '13 at 19:31
  • $\begingroup$ The 2-approximation is also optimal under the usual assumptions. $\endgroup$
    – Juho
    Dec 29 '13 at 13:50
  • $\begingroup$ @Suresh thx do you know any refs for that? $\endgroup$
    – vzn
    Aug 8 '14 at 16:47

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.