The Minimum Wiener Connector Problem
Natali Ruchansky
Computer Science Dept.
Boston University, USA
natalir@bu.edu

Francesco Bonchi David García-Soriano
Francesco Gullo Nicolas Kourtellis
Yahoo Labs, Barcelona
{bonchi,davidgs,gullo,kourtell}@yahoo-inc.com

arXiv:1504.00513v2 [cs.SI] 16 Oct 2016

ABSTRACT
The Wiener index of a graph is the sum of all pairwise
shortest-path distances between its vertices. In this paper
we study the novel problem of finding a minimum Wiener
connector : given a connected graph G = (V, E) and a set
Q ⊆ V of query vertices, find a subgraph of G that connects
all query vertices and has minimum Wiener index.
We show that Min Wiener Connector admits a
polynomial-time (albeit impractical) exact algorithm for the
special case where the number of query vertices is bounded.
We show that in general the problem is NP-hard, and has no
PTAS unless P = NP. Our main contribution is a constante
factor approximation algorithm running in time O(|Q||E|).
A thorough experimentation on a large variety of realworld graphs confirms that our method returns smaller and
denser solutions than other methods, and does so by adding
to the query set Q a small number of “important” vertices
(i.e., vertices with high centrality).

1.

INTRODUCTION

Suppose we have identified a set of subjects in a terrorist network suspected of organizing an attack. Which other
subjects, likely to be involved, should we keep under control? Similarly, given a set of patients infected with a viral
disease, which other people should we monitor? Given a set
of proteins of interest, which other proteins participate in
pathways with them?
Each of these questions can be modeled as a graph-query
problem: given a graph G = (V, E) and a set of query vertices Q ⊆ V , find a subgraph H of G which “explains” the
connections existing among the nodes in Q, that is to say
that H must be connected and contain all query vertices
in Q. We call this query-dependent subgraph a connector.
While there exist many methods for query-dependent subgraph extraction (discussed later in Section 1.1), the bulk of
this literature aims at finding a “community” around the
set of query vertices Q: the implicit assumption is that the
vertices in Q belong to the same community, and a good solution will contain other vertices belonging to the same comPermission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are not
made or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for components
of this work owned by others than ACM must be honored. Abstracting with
credit is permitted. To copy otherwise, or republish, to post on servers or to
redistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
SIGMOD’15, May 31–June 4, 2015, Melbourne, Victoria, Australia.
Copyright c 2015 ACM 978-1-4503-2758-9/15/05 ...$15.00.
http://dx.doi.org/10.1145/2723372.2749449.

munity of Q. When such an assumption is satisfied, these
methods return reasonable subgraphs. But when the query
vertices belong to different modules of the input graph, these
methods tend to return too large a subgraph, often so large
as to be meaningless and unusable in real applications.
The goal of this paper is different, as we do not aim at reconstructing a community. Instead we seek a small connector: a connected subgraph of the input graph which contains
Q and a small set of important additional vertices. These additional vertices could explain the relation among the vertices in Q, or could participate in some function by acting
as important links among the vertices in Q. We achieve this
by defining a new, parameter-free problem where, although
the size of the solution connector is left unconstrained, the
objective function itself takes care of keeping it small.
Specifically, given a graph G = (V, E) and a set of query
vertices Q ⊆ V , our problem asks for the connector H ∗ minimizing the sum of shortest-path distances among all pairs
of vertices (i.e., the Wiener index [57]) in the solution H ∗ :
X
H ∗ = arg min
dG[S] (u, v)
G[S]:Q⊆S⊆V

{u,v}∈S

where G[S] denotes the subgraph induced by a set of
nodes S, and dG[S] (u, v) denotes the shortest-path distance
between nodes u and v in G[S]. We call H ∗ the minimum
Wiener connector for query Q.
This is a very natural problem to study: shortest paths
define fundamental structural properties of graphs, playing
a role in all the basic mechanisms of networks such as their
evolution [39] and the formation of communities [26]. The
fraction of shortest paths that a vertex takes part in is called
its betweenness centrality [8], and is a well established measure of the importance of a vertex, i.e., the extent to which
an actor has control over information flow. As our experiments in Section 6 show, a consequence of our definition
of minimum Wiener connector is that our solutions tend
to include vertices which hold an important position in the
network, i.e., vertices with high betweenness centrality.
Consider social and biological networks with their modular structure [26] (i.e., the existence of communities of vertices densely connected inside, and sparsely connected with
the outside). When the query vertices Q belong to the same
community, the additional nodes added to Q to form the
minimum Wiener connector will tend to belong to the same
community. In particular, these will typically be vertices
with higher “centrality” than those in Q: these are likely to
be influential vertices playing leadership roles in the community. These might be good users for spreading information,
or to target for a viral marketing campaign [34].

Figure 1: Example of two minimum Wiener connectors on
the Zachary’s “karate club” social network: on the left the
query vertices Q (in dark gray) belong to different communities, on the right they belong to the same community.
Instead, when the query vertices in Q belong to different
communities, the additional vertices added to Q to form the
minimum Wiener connector will contain vertices adjacent
to edges that “bridge” the different communities. These also
have strategic importance: information has to go over these
bridges to propagate from a community to others, thus the
vertices incident to bridges enjoy a strategically favorable
position because they can block information, or access it
before other individuals in their community. These vertices
are said to span a “structural hole” [9]: they are the best
candidates to target for blocking the spread of rumors or
viral diseases in a social network, or the spread of malware
in a network of computers. In a protein-protein interaction
network these vertices can represent proteins that play a key
role in linking modules and whose removal can have different
phenotypic effects.
As an example, consider the classic Zachary’s “karate
club” toy social network [60] with known community structure: a dispute between the club president (vertex 34) and
the instructor (vertex 1) led to the club splitting into two.
In Figure 1 we show two different minimum Wiener connectors: the one on the left has the query nodes Q (in dark
gray) belonging to the two different communities, while in
the example on the right, all the query vertices belong to
the same community. As discussed above, we can observe
that when the query vertices span over different communities, the minimum Wiener connector will include vertices
incident to bridging edges. This is the case in our example in
Figure 1 (left): given Q = {12, 25, 26, 30} the solution subgraph H ∗ adds to Q the vertices 1 and 34 (the leaders of the
two communities) and the vertex 32, which is one of the few
vertices connecting 1 and 34 (which do not have a direct connection) and thus practically bridging the two communities.
By contrast, in the example on the right, the query vertices
Q = {4, 12, 17} belong to the same community, and as expected the solution remains inside the community: in this
case we just add two vertices, one of which is the community
leader (vertex 1), which holds a very central position.

1.1

Related work

At a high level our problem can be described as the problem of finding an interesting connected subgraph of G containing a set of query vertices Q. Several problems of this
type have been studied under different names, depending on
the objective function adopted: local community detection,
seed set expansion, connectivity subgraphs, just to mention

a few. As discussed above, most of the existing approaches
aim at finding a community around the seeds in Q: these
methods end up producing very large solutions, especially
when the query vertices are not in the same community. Our
goal instead is to produce a small connector by adding a few
central vertices. Another important distinction is that many
researchers have considered only the cases where |Q| = 1 [3,
14, 15, 31] or |Q| = 2 [19]. Finally, our method is parameterfree, while several existing methods have many parameters
which make a direct comparison complicated. In the following we provide a brief overview of this body of literature,
highlighting the distinctions w.r.t. our proposal.
Random-walk methods. Many authors have adopted
random-walk-based approaches to the problem of finding
vertices related to a seed of vertices: this is the basic idea
of Personalized PageRank [33, 29]. Spielman and Teng propose methods that start with a seed and sort all other vertices by their degree-normalized PageRank with respect to
the seed [49]. Andersen and Lang [2] and Andersen et al. [1]
build on these methods to formulate an algorithm for detecting overlapping communities in networks. In a recent work,
Kloumann and Kleinberg [37] provide a systematic evaluation of different methods for seed set expansion on graphs
with known community structure. They assume that the
seed set Q is made of vertices belonging to the same community C: under this assumption they measure precision and
recall in reconstructing C. Their main findings are that (i)
PageRank-based methods outperform other methods, (ii)
few iterations (two or three) of the PageRank update rule
are sufficient for convergence, and (iii) standard PageRank
is to be preferred over degree-normalized PageRank [2, 1].
Closer to our goals, Faloutsos et al. [19] address the problem of finding a subgraph that connects two query vertices
(|Q| = 2) and contains at most b other vertices, optimizing a
measure of proximity based on electrical-current flows. Tong
and Faloutsos [53] extend the work of [19] to deal with query
sets of any size, but again having a budget b of additional
vertices. They introduce the concept of Center-piece Subgraph, the computation of which is based on the Hadamard
(i.e., component-wise) product of a set of vectors, where
each vector is obtained by doing a random walk with restart
from a query vertex. The efficiency and scalability of the
method is severely limited by the processing time of random
walks with restart. Koren et al. [38] redefine proximity using
the notion of cycle-free effective conductance and propose a
branch and bound algorithm.
All the approaches described above require several parameters: common to all is the size of the required solution,
plus all the usual parameters of PageRank methods, e.g.,
the jumpback probability, or the number of iterations. We
recall that instead our problem definition and algorithms are
completely parameter-free.
Other methods. Asur and Parthasarathy [3] introduce the
concept of viewpoint neighborhood analysis in order to identify neighbors of interest to a particular source in a dynamically evolving network. The authors also show a connection
of their measure with heat diffusion. However, the method
of Asur and Parthasarathy has several parameters, such as
the budget, the stopping threshold, and minimum number
of viewpoint neighborhoods for a vertex.
More recently, Sozio and Gionis [48] provide a parameterfree combinatorial optimization formulation. Their problem
asks to find a connected subgraph containing Q and max-

imizing the minimum degree. Sozio and Gionis show that
the problem is solvable in polynomial time and propose an
efficient algorithm. However, their algorithm tends to return extremely large solutions (it should be noted that for
the same query Q many different optimal solutions of different sizes exist). To circumnavigate this drawback they
also study a constrained version of their problem, with an
upper bound on the size of the output community. In this
case the problem becomes NP-hard. The authors propose
a heuristic where the quality of the solution produced (i.e.,
its minimum degree) can be arbitrarily far away from the
optimal value of a solution to the unconstrained problem.
Cui et al. [15] propose a local-search method to improve
the efficiency of the algorithm by Sozio and Gionis [48]; however, their method does not solve the issue of the size of the
solutions produced. Moreover, their method works only for
the special case |Q| = 1.
Steiner Tree and MAD Spanning Trees. Given a graph
and a set of terminal vertices, the Steiner tree problem asks
to find a minimum-cost tree that connects all terminals.
This is an extremely well-studied problem: a plethora of
methods to solve/approximate it and many variants of the
problem have been defined [22]. We will explain in detail
(Section 2) how our Min Wiener Connector problem differs from the Steiner tree problem.
Another related problem is Minimum Average Distance (MAD) Spanning Trees: given a graph G, find a spanning tree of G that minimizes the average shortest-path distance among all pairs of vertices [30]. This problem is related
to Wiener index as a MAD Spanning Tree is a spanning tree
that minimizes the Wiener index. However, this problem
still remains different from our Min Wiener Connector
as the latter asks for subgraphs containing a given set of
query vertices rather than asking to span the whole input
graph. In a sense, our problem is to MAD Spanning Trees
as Steiner Tree is to Minimum Spanning Tree.
Wiener index. The notion of Wiener index is rooted in
chemistry, where in 1947 Harry Wiener introduced it to characterize the topology of chemical compounds [57]. In general, the Wiener index captures how well connected a set of
vertices are, thus bearing resemblance to centrality measures
and finding application in several fields, such as communication theory, facility location, and cryptography [18]. A
recent work also considers the Wiener index in the context
of event detection in activity networks [46]. Existing literature on Wiener index focuses on computing it efficiently [42],
finding a tree that minimizes/maximizes it among all trees
with a prescribed degree sequence [56, 61, 11], characterizing the trees which minimize [21] or maximize [21, 50] the
Wiener index among all trees of a given size and maximum
degree, or solving the inverse Wiener index problem [20].
To the best of our knowledge, the problem of finding a
minimum-Wiener-index subgraph containing a given set of
query vertices has never been studied before.
In our experiments in Section 6 we will compare our
method with prior contributions which allow |Q| > 2: following the findings of [37] we will use a standard PageRank
(with no normalization) personalized over the query vertices
Q (ppr for short), the so-called Center-piece Subgraph [53]
(cps for short) which is closer in spirit to our goal of finding a connector and not a community, the so-called Cocktail
Party Problem [48] (ctp) which is parameter free, and the
classic Steiner Tree (st for short).

1.2

Contributions and roadmap

In this paper we initiate the study of the Min Wiener
Connector problem, a novel parameter-free graph query
problem, whose objective function favors small connected
subgraphs, obtained by adding few central vertices to the
query vertices. Beyond this main contribution, we provide
a series of theoretical and empirical results:
• We show that, when the number of query vertices is
small, Min Wiener Connector can be solved exactly
in polynomial time (§3). However, in the general case
our problem is NP-hard and it has no PTAS unless
P = NP (§2): note that, while the inapproximability
result says that the problem cannot be approximated
within every constant, it leaves open the possibility of
approximating it within some constant.
• In fact, our central result is an efficient constant-factor
approximation algorithm for Min Wiener Connector
e
(§4), which runs in O(|Q||E|)
time.
• We devise integer-programming formulations of our
problem (§5). We use them to compare our solutions
for small graphs with those found using state-of-the art
solvers, and show empirically that our solutions are indeed close to optimal (§6.2).
• We empirically confirm that existing methods for querydependent community extraction tend to produce large
solutions, which become even larger when the query
set Q is made of vertices belonging to different communities (§6.4). Our method instead produces solution
subgraphs which are smaller in size, denser, and which
include more central nodes (§6.3), regardless of whether
the query vertices belong to the same community or not.
• We show interesting case-studies in biological and social
networks, confirming that our method returns small solutions that include important vertices (§7).

2.

PROBLEM STATEMENT

Preliminaries. We consider simple, connected, undirected,
unweighted graphs. We denote the vertex set (resp., edge
set) of a graph G by V (G) (resp., E(G)).
Given a graph G and S ⊆ V (G), we denote by G[S] the
subgraph of G induced by S: G[S] = (S, E|S), where E|S =
{(u, v) ∈ E | u ∈ S, v ∈ S}. For any connected graph H and
u, v ∈ V (H), let dH (u, v) denote the shortest-path distance
between u and v in H. Clearly, if H is a subgraph of G, it
holds that dG (u, v) ≤ dH (u, v).
The Wiener index W(H) of a (sub)graph H is the sum
of pairwise distances between vertices in H [57]:
X
W(H) =
dH (u, v),
(1)
{u,v}⊆V (H)

where the sum is taken over unordered pairs.
For ease of notation, we identify any S ⊆ V (G) with its
induced subgraph G[S]. Thus, we use the shorthand dS (u, v)
(resp., W(S)) to denote dG[S] (u, v) (resp., W(G[S]).
The input to our problem is a connected graph G and a
set Q ⊆ V (G) of query vertices (or terminals). A connector
for Q in G is a connected subgraph of G containing Q.
Problem definition. In this work we aim at finding subgraphs of the input graph that connect a given set of query
vertices while minimizing the Wiener index.

r1

Problem 1 (Min Wiener Connector). Given
a
graph G = (V, E) and a query set Q ⊆ V , find a connector
H ∗ for Q in G with the smallest Wiener index.
Clearly we may restrict the search to vertex sets and their
corresponding induced subgraphs.

Note that W(H) may be written as the product of |V (H)|
2
and the average distance between pairs of distinct vertices
of H. Therefore, Problem 1 encourages solutions that attain
a proper tradeoff between having small pairwise distances
and using few vertices. In fact, while adding vertices may
decrease distances, it also increases the number of terms to
be summed up in Eq (1).
Hardness results. We next prove that the problem is NPhard, hence unlikely to admit efficient exact solutions. In
fact we show a stronger result, namely that it does not admit
a polynomial-time approximation scheme: unless P = NP,
one cannot obtain a polynomial-time c-factor approximation
algorithm for every c > 1. This inapproximability result
says that the problem cannot be approximated within every
constant, but leaves open the possibility of approximating it
to some constant; in fact we will show this possible.
Our proof makes use of the following inapproximability
result for Vertex Cover in Bounded Degree Graphs:
Theorem 1 (Dinur and Safra [17]). There
exist
constants d ∈ N, α ∈ R+ with the following property: given
a degree-d graph G and an integer k ∈ N, it is NP-hard to
distinguish instances where the minimum vertex cover of
G has size larger than k(1 + α) from instances where the
minimum vertex cover of G has size at most k.
Theorem 2. There is some constant ε ∈ R+ such that
Problem 1 is NP-hard to approximate within a 1 + ε factor.
Proof. We present a gap-preserving reduction from
Vertex Cover in Bounded Degree Graphs to Min
Wiener Connector. Let α and d be as in Theorem 1.
Let hG, ki be an instance of the decision version of Vertex
Cover in Bounded Degree Graphs, where the degree of
G is at most d. We need to show that there is some constant
ε > 0 such that, given hG, ki, we can construct in polynomial time an instance hG0 , Qi of Min Wiener Connector
and a bound B ∈ N with the following properties:
(a) if G has a vertex cover of size at most k, then hG0 , Qi
has a connector with Wiener index at most B;
(b) if every vertex cover of G has size larger than k(1 + α),
then every connector of hG0 , Qi has Wiener index larger
than B(1 + ε).
Let G have n vertices and m edges. We may assume that
, for otherwise the vertex cover instance can be
m≥k≥ m
d
answered trivially. Furthermore, for any fixed constant c we
may assume that k > c · d (if not, we can solve the vertex
cover instance in polynomial time.)
Our graph G0 is built as follows. Let the vertex set of G0
be composed of:
• a distinguished “root” node r;
• n vertices v1 , . . . , vn corresponding to vertices of G;
• m vertices e1 , . . . , em corresponding to edges of G.
Put an edge between r and every vertex in {v1 , . . . , vn },
and connect vi to ej if and only if vi is an endpoint of ej

V1

V2

V3

r2

V4

V5

V6

V7

V8

V9

V10

Figure 2: Example showing that a solution to Steiner
Tree may exhibit a large Wiener index. Note that similar
situations arise also in real-world instances (see §6.4).
in G. Note that to every vi correspond at most d such
ej ’s, and the degree of each ej is exactly two. Finally, let
Q = {e1 , . . . , em } ∪ {r} be the set of query vertices.
Observe that any solution to the original Vertex Cover
instance gives rise to a feasible solution to Min Wiener
Connector that contains Q and a subset X ⊆ {v1 , . . . , vs };
conversely, any solution to Min Wiener Connector is of
the form Q ∪ X , where X ⊆ {v1 , . . . , vs } is a vertex subset
whose corresponding vertices in G cover all the edges of G.
We claim that, if |X | = t and Q ∪ X forms a connected
subgraph, then the Wiener index of the induced subgraph
of G0 containing Q and X is at most u(t) = t2 + 3mt + 2m2
and at least l(t) = u(t)−O(md). Indeed, the contribution to
the Wiener index from r to the t chosen vertices is exactly t,
and its contribution to the m edges is exactly 2m. The sum
of induced distances among the t chosen vertices is precisely
t
· 2 = t2 − t. The contribution of the t chosen vertices to
2
e1 , . . . , en is t(3m − O(d)), because the distance from vi to
ej is exactly 3 except in the case that ej has an edge to vi
(meaning that ej was an endpoint of vi in the original graph
G, and there are at most d such edges for any vi ). Similarly,
the contribution from e1 , . . . , em to themselves is 12 m(4m −
O(d)) = 2m2 −O(md). The total is t2 +2m2 +3tm−O(md).
If we pick B = u(k), we know that condition (a) is satisfied. Regarding condition (b), a straightforward computation shows that u(k) ≤ 6d2 k2 and u(k(1+α)) ≥ u(k)+5αk2 ,
hence using the fact that m ≤ kd we get
5αk2 − O(md)
O(1)
l((1 + α)k) − u(k)
5α
≥
≥ 2 −
.
u(k)
6d2 k2
6d
k
For some large enough k0 = Θ(d2 /α), let ε =
the above shows that ε > 0 and

5α
6d2

−

O(1)
;
k0

l((1 + α)k) − u(k)
> ε,
u(k)
so condition (b) holds as well, completing the proof.
Min Wiener Connector vs. Steiner tree. At first
glance, Problem 1 may resemble the well-known Steiner
Tree problem (see, e.g, [22]): given a graph G and a set Q
of terminal vertices of G, find a minimum-sized connector
for Q. (The size is measured as the total cost of edges used,
which for unweighted graphs is one less than the number of
vertices used.) Such an optimal subgraph must be a tree.
Although related (see Section 4), the two problems are
different. In fact, a solution for Steiner Tree may be arbitrarily bad for Min Wiener Connector. To see this, take
a look at the graph in Figure 2. Let Q = {v1 , . . . , v10 }
be the set of query/terminal vertices. The unique optimal solution to the Steiner Tree problem is obviously
Q itself, which has Wiener index W(Q) = 165. However, adding either vertex r1 or r2 would lower the index
to W(Q ∪ {r1 }) = W(Q ∪ {r2 }) = 151, and the optimal
solution to our Min Wiener Connector problem is given
by Q ∪ {r1 , r2 }, which has Wiener index 142. Also note that

no tree is an optimal solution to this example, showing that
the addition of extra edges may help decrease the cost.
In general, the fact that the Steiner Tree problem seeks
connectors with as few edges/vertices as possible hinders the
minimization of pairwise distances. We can generalize the
example in Figure 2 to a line of length h and a root r connected to all of them. The optimal Steiner Tree solution
exhibits a Wiener index of Ω(h3 ), determined by the Ω(h2 )
pairs of vertices and an average distance of Ω(h); on the
other hand, a solution to Min Wiener Connector can include r so as to achieve constant average distance, lowering
the Wiener index to O(h2 ).

3.

AN EXACT ALGORITHM

Here we address the question of how to solve the Min
Wiener Connector problem exactly. If the input graph
has n vertices, a straightforward solution would be to try
all 2n vertex subsets and compute their Wiener index; this
gives a running time of 2n poly(n). On the other hand, there
are some polynomial-time solvable special cases. As an example, for unweighted graphs (like the ones studied in this
work), when |Q| = 2, any shortest path between the two terminals yields an optimal solution. As many problems like
satisfiability, coloring, etc., turn from easy to NP-hard as
the “size” parameter switches from 2 to 3, it is natural to
wonder if the same happens here. Interestingly, the answer
is negative: the problem admits an exact algorithm that
runs in polynomial time for any fixed bound on the maximum size of the query set. The result is of limited practical
interest, but gives insight into the nature of the problem.
Theorem 3. The Min Wiener Connector problem
can be solved in polynomial time when |Q| = O(1).
That is, there is a function f : N → N such that the Min
Wiener Connector problem can be solved in time nf (|Q|) .
The proof is in Appendix A.1. The intuition is that an optimal solution has f (|Q|) = poly(|Q|) “pivotal” vertices that
are useful in connecting several query vertices together or are
query vertices themselves. Any other vertices in the solution
are simply “pass-through” vertices needed to connect pairs
of pivotal vertices via shortest paths; they could be replaced
by vertices in another arbitrary shortest path between the
required pivotal vertices. Thus, if we try all possible sets of
pivotal vertices and connection patterns among them, and
then find shortest paths in G to actually connect them, we
are guaranteed to find an optimal solution.

4.

AN APPROXIMATION ALGORITHM

As we cannot hope for efficient exact solutions to Min
Wiener Connector, in this section we design an efficient
algorithm with provable approximation guarantees. Specifically, we achieve a constant-factor approximation in roughly
the same time it takes to compute shortest-path distances
from the terminals to every other vertex in the graph.
Proof outline. We need to introduce a series of relaxations of Min Wiener Connector to arrive at a problem for which it is easier to derive an approximation algorithm. First we show that we can approximate the cost of
any solution in terms of the number of vertices in it and
the single-source shortest-path distances to a suitably chosen root vertex r ∈ V (G). Then we introduce a further

relaxation where distances are measured according to the
original graph; using the techniques developed by [35] to
find light approximate shortest path trees, we show how to
make use of a solution to this relaxation. Then we apply
a linearization technique to show that if we knew a certain
parameter λ controlling the ratio between the size of the optimal solution and the sum of distances to r in the optimal
solution, we could reduce our problem to Node-weighted
Steiner Tree. It turns out that our particular instances
of the latter problem admit an O(1)-approximation (unlike
the general case). Finally, we explain how to search quickly
for the correct values of r and λ; as an optimization, we also
prove that we can further restrict the search of candidates
for r. Finally, we combine these arguments to prove the
correctness and efficiency of our algorithm.
Step 1: from Min Wiener Connector to Min-A Connector. First we need the following lemma, whose proof
may be found in Appendix A.2.
Lemma 1. For any graph H,
X
X
2 W (H)
≤ 2 min
dH (v, r).
min
dH (v, r) ≤
r∈V (H)
r∈V (H)
|V (H)|
v∈V (H)

v∈V (H)

Lemma 1 justifies the introduction of the following problem. Given a subgraph H of G and r ∈ V (H), let
X
A(H, r) = |V (H)| ·
dH (u, r)
u∈V (H)

A(H)

=

min A(V (H), r).
r∈V (H)

Problem 2 (Min-A Connector). Given a graph G
and a query set Q ⊆ V (G), find a connector H for Q in
G minimizing A(H).
Note that standard Steiner tree problems do not minimize
A(H), but the number (or total cost) of the edges in H.
Corollary 1. Any α-approximate solution to Problem 2
is a 2α-approximate solution to Min Wiener Connector.
Step 2: from Min-A Connector to Min Weak-A
Rooted Connector via distance adjustments. One approach to solve Problem 1 is to “guess” the correct vertex r
and then find a connector H for Q that minimizes A(H, r).
However, the objective function depends on the induced distances of the unknown solution. In order to simplify our
task, we now introduce a “weak” relaxation of the above
problem where shortest-path distances are measured in the
input graph G instead.
Given a subgraph H of G and a vertex r ∈ V (H), define
e
A(H,
r) = |V (H)| ·

X

dG (u, r)

(2)

u∈V (H)

Problem 3 (Min Weak-A Rooted Connector).
Given graph G, root r ∈ V (G) and query set Q ⊆ V (G),
e ).
find a Steiner tree T for Q in G minimizing A(T
Here we insist that the solution be a tree (unlike in Problem 2, where we allowed non-tree solutions, even though an
optimal solution may easily seen to be a tree as well). The
reason will become apparent shortly.

We are now faced with an additional complication, namely
that a good solution to Min Weak-A Rooted Connector may not give a good solution to Min-A Connector.
Hence the need to perform a post-processing step on every
candidate solution to ensure that distances in the modified
solution resembles distances in G as closely as possible.
Lemma 2. Let T be a subtree of G and r ∈ V (T ). There
is another subtree T 0 of G with the following properties:
(a) V (T 0 ) ⊇ V (T );
√
(b) |V (T 0 )| ≤ (1 + 2)|V (T )|;
√
(c) for all v ∈ V (T 0 ), dT 0 (r, v) ≤ (1 + 2) dG (r, v).
√ P
P
(d)
2 v∈V (T ) dG (r, v).
v∈V (T 0 ) dG (r, v) ≤
Furthermore, given T , a BFS tree from r in G, and dG (r, v)
for all v ∈ V (G), it is possible to construct T 0 in time
O(|V (T )|).
This follows from a slight modification of an algorithm by
Khuller et al for balancing spanning trees and shortest-path
trees [35, Lemma 3.2]; although they state it for minimum
spanning trees and shortest path trees with the same vertex
set, a careful examination of their proof establishes Lemma 2
as well. For completeness, we reproduce the proof in Appendix A.3.
Corollary 2. Any α-approximation
to Problem 3 can
√
be used to obtain a (4 + 3 2)α-approximation to Problem 2.
Proof. We can try all possible choices of r. For each of
them, let T be an α-approximation to Problem 3. Then we
can find a tree T 0 as in Lemma 2. Since V (T ) ⊆ V (T 0 ), T 0
is also a connector for Q and satisfies
X
e 0 , r) = |V (T 0 )|
A(T
dG (r, v)
v∈V (T 0 )

≤ (1 +

√

2) |V (T )|

X

dG (r, v)

v∈V (T 0 )

≤ (1 +

√

2)

X
√
2 |V (T )|
dG (r, v)
v∈V (T )

√
e
= (2 + 2) A(T,
r),
√
√
e 0 , r) ≤ (4 + 3 2)A(T,
e
r).
and A(T 0 , r) ≤ (1 + 2)A(T
Step 3: from Min Weak-A Rooted Connector to
Min-B Rooted Steiner Tree. We further relax Problem 3 so as to employ a modified objective function where
the product between the number of vertices in H and the
sum of original distances to the chosen root r is replaced
with a linear combination of the two. The rationale here is
to make the overall objective function linear and, as such,
more amenable to standard approximation techniques.
Given (a subgraph induced by) a subset of vertices H ⊆
V (G), a root vertex r ∈ V (H), and a parameter λ ∈ R+ ,
the modified objective we consider is:
P
u∈V (H) dG (r, u)
.
(3)
B(H, r, λ) = λ |H| +
λ
Problem 4 (Min-B Rooted Steiner Tree). Given
a graph G, a query set Q ⊆ V (G), a root vertex r ∈ V , and
a parameter λ ∈ R+ , find a Steiner tree for Q ∪ {r} in G
minimizing B(H, r, λ).

We next show that, by choosing λ in the proper way, any
approximate solution to Problem 4 yields an approximate
solution to Problem 3 too. The right choice of λ is given by
the following lemma, proved in Appendix A.4.
Lemma 3. For any graph G with |V (G)| ≥√2, p
query set
Q ⊆ V (G) and r ∈ V (G), there is λ ∈ [1/ 2, |V (G)|]
such that for any α ∈ R+ , every α-approximate solution to
Problem 4 is also an α2 -approximate solution to Problem 3.
Step 4: approximating Min-B Rooted Steiner Tree.
Our next step aims to find approximate solutions to Problem 4. To this end, we note that Problem 4 can be cast as a
Node-weighted Steiner Tree problem, where the cost of
a node u is equal to λ + dG (r, u)/λ. However, no approximation factor better than Ω(log |Q|) is possible in general for
Node-weighted Steiner Tree, unless every problem in
NP can be solved in quasipolynomial time [36]. Nevertheless, we show that our particular problem admits a constantfactor approximation, by shifting the cost from vertices to
edges and reducing it to a classical Steiner Tree problem.
The reason is that in our instance the cost of two adjacent
vertices from the root r cannot differ by more than 1, thus
the overall solution cost is nearly preserved despite the cost
shift. We formalize this intuition next.
Lemma 4. Given a graph G = (V, E), a query set Q ⊆ V ,
a root vertex r ∈ V , and a parameter λ ∈ R+ , let Gr,λ be a
weighted graph with vertex set V , edge set E, and weight on
G (r,v)}
.
each edge (u, v) equal to w(u, v) = λ + max{dG (r,u),d
λ
Then any Steiner tree T for Q ∪ {r} satisfies the following:
X
B(T, r, λ) − λ ≤
w(u, v) ≤ 2 (B(T, r, λ) − λ).
(u,v)∈E(T )

Proof. Observe that the cost w(u, v) of each edge
(u, v) ∈ E(T ) lies in the range [λ+dG (r, u)/λ, λ+(dG (r, u)+
1)/λ], as u and v are adjacent in T . Notice that in every
edge (u, v) of T , either u is the parent of v or v is the parent
of u. Hence, writing A = V (T ) \ {r}, we can bound
X
X dG (r, u)+1
X dG (r, u) 
≤
w(u, v) ≤
λ+
,
λ+
λ
λ
u∈A
u∈A
(u,v)∈E(T )
|
{z
}
B(T,r,λ)−λ

The result follows by noticing that the right-hand side is at
most
|V (T )| − 1
B(T, r, λ) − λ +
≤ 2 (B(T, r, λ) − λ).
λ
Lemma 4 entails a reduction from Problem 4 to the wellstudied Steiner Tree tree problem. The best known algorithm for the latter is the 1.39-factor approximation algorithm of Byrka et al. [10]. However, it is based on solving
a linear program, in contrast to quicker combinatorial algorithms that achieve a factor-2 approximation. The fastest
among the latter is due to Mehlhorn [41].
Corollary 3. A 4-approximation to Problem 4 can be
computed in time O(|E|+|V | log |V |), provided that shortestpath distances from Q in G have been precomputed.
Proof. We can construct the graph of Lemma 4 in time
O(|V | + |E|), and use the 2-approximation algorithm of [41]
for Steiner tree, which runs in time O(|E| + |V | log |V |). By
Lemma 4, the result is a 4-approximation for Problem 4.

Step 5: choosing r and λ. At this point, we know that,
with the right choice of λ (which depends on the problem
instance), we can get a constant-factor approximate solution
to Problem 3. For any given graph G and query set Q ⊆
V (G), the algorithm would run as follows:
• For every vertex r ∈ V do:
• Compute dG (r, u) from r to every other vertex u;
• Guess λ matching the value stated in Lemma 3;
• Construct the weighted graph Gr,λ of Lemma 4;
• Find an α-approximate solution Sr∗ to the Steiner
Tree problem on graph Gr,λ and terminals Q∪{r};
• Take the Sr∗ that minimizes B(Sr∗ , r, λ).
However, we still need to explain how to guess λ. Since
there are only poly(|V (G)|) many possible values for λ2 , we
could try all of them in polynomial time. A faster way is
to fix some
0 and then try all powers of (1 + β) in the
p β >p
interval [ 1/2, |V |], of which there are only O(log |V |/β)
many; this will guarantee that one of the candidate values
of λ tried will be off by a factor of at most 1+β. It is not hard
to generalize Lemma 3 to show that using a 1 + β approximation for the true value of λ results in the loss of another
multiplicative (1 + β)2 factor in the overall approximation.
Step 6: restricting the number of root vertices. Finally, we show that trying all possible root vertices r ∈ V
is overkill if we are willing to settle for a somewhat larger
approximation factor. The next result shows that we can
restrict our search to elements of the query set (notice that
an optimal solution to Problem 2 is a tree with leaves in Q).
Lemma 5. Let T be a tree, r ∈P V (T ), and let x∗
∗
be a leaf of T closest to r. Then
u∈V (T ) dT (x , u) ≤
P
∗
3
u∈V (T ) dT (r, u), hence A(T, x ) ≤ 3 · A(T, r).
d(x) =
PProof. For any vertex x ∈ V (T ), let
∗
d
(u,
x).
It
suffices
to
show
that
d(x
)
−
d(r) ≤
T
u∈V (T )
2d(r). To this end, partition V (T ) into levels according
to the distance to r: Li = {u ∈ V (T ) | dT (r, u)
S = i}.
Let ` = dT (r, x∗ ) and for t ∈ N write L≤t = j≤t Lj ,
S
L>t = j>t Lj . On the one hand,
X
d(x∗ ) − d(r) =
(dT (u, x∗ ) − dT (u, r))
(4)
u∈V (T )

≤

X

|dT (u, x∗ ) − dT (u, r)| ≤ (|L≤` | + |L>` |) `.

u∈V (T )

On the other hand, observe that by our choice of x∗ , it is
guaranteed that |L0 | ≤ |L1 | ≤ . . . ≤ |L` |, as every vertex
at level i < ` has at least one child (and they are distinct
as H is acyclic). This implies that we can partition L≤`
into a collection of pairs {a, b} where a 6= b and dT (r, a) +
dT (r, b) ≥ `, possibly along with a singleton element from
L≥`/2 . Therefore, the average distance from the elements of
L≤` to r is at least `/2. Furthermore, every element of L>`
is at distance > ` from r by definition. Hence
`
+ |L>` |(` + 1).
2
Combining Equations (4) and (5) yields the result.
d(r) ≥ |L≤` |

(5)

Putting it all together. The pseudocode for our approach
is shown as Algorithm 1. The following theorem summarizes
the results about solution quality and running time.

Algorithm 1 WienerSteiner
Input: A graph G = (V, E); a set of query vertices Q ⊆ V .
Output: A set of vertices Q ⊆ H ∗ ⊆ V .

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

For all q ∈ Q and for all u ∈ V , compute dG (q, u)
H=∅
. set of candidate solutions
β ← any constant > 0
. e.g., β = 1
for t = 1, . . . , dlog1+β |V |e do
λ ← (1 + β)t
. guess the right balance
for r ∈ Q do
. guess a “root” vertex
. Compute Gr,λ = (V, E, w) (Lemma 4)
for (u, v) ∈ E do
max{dG (r,u),dG (r,v)}
w(u, v) ← λ +
λ
end for
T ← ApproxSteinerTree(Gr,λ , Q)
H ← AdjustDistances(T )
. see Lemma 2
H ← H ∪ {(H, r)}
end for
end for
H ∗ ← arg min(H,r)∈H A(H, r)
. see Remark 1

Theorem 4. There is a constant-factor approximation
algorithm for the Min Wiener Connector
problem run
ning in O |Q| (|E| log |V | + |V | log2 |V |) .
Proof. First we prove correctness. Let H denote an optimal solution to Min Wiener Connector. By Lemma 1,
A(H) ≤ 2 · W(H), so there is r ∈ V (H) with A(H, r) ≤
2 · W (H). By Lemma 5, there exists q ∈ Q with A(H, q) ≤
3 · A(H, r) ≤ 6 · W(H); henceforth we take q to be the
“root” vertex in our problems. Let K denote an optie
mal solution to Problem 3 with root q; clearly A(K,
q) ≤
+
e
A(H, q) ≤ A(H, q). Let λ ∈ R be as in Lemma 3, and let
L ⊆ V (G) be an optimal solution to Problem 4. Then for
any connector X, the conclusion of Lemma 3 says that if
e
e
q).
B(X, q, λ) ≤ αB(L, q, λ), then A(X,
q) ≤ α2 A(K,
The main loop is guaranteed to try at some point this
choice of q and also a (1 + β)-approximation λ0 for λ. It is
readily seen that, for any Y , B(Y, q, λ0 ) ≤ (1 + β)B(Y, q, λ).
By Corollary 3, we can find an 4-factor approximation to
Problem 4 with q and λ0 ; in particular we find X, q and λ0
with B(X, q, λ0 ) ≤ 4B(L, q, λ0 ) ≤ 4(1 + β)B(L, q, λ). Theree
e
q) ≤ 96(1 + β)2 W(H).
fore A(X,
q) ≤ 16(1 + β)2 A(K,
By Corollary 2, line 11 obtains a graph X 0 with
√
√
e
A(X 0 , q) ≤ (4 + 3 2)A(X,
q) ≤ 96(1 + β)2 (4 + 3 2)W (H).
Therefore, another application of Lemma 1 tells us that
W(X 0 ) ≤ A(X 0 , r) ≤ 792(1 + β)2 W(H) = O(W(H)),
as we wished to prove.
As for the running time, computing the initial shortestpath distances (Line 1) takes O(|Q| (|V | + |E|)) time, while
the main loop in Lines 3–14 is repeated O(|Q| log |V |) times.
Lines 6–10 compute the weighted graph Gr,λ and find an
approximated Steiner tree, thereby solving Problem 4. By
Corollary 3, they run in time O(|E| + |V | log |V |). Line 11
adjusts large distances and run in linear time (Lemma 2).
Finally, computing A(H, r) in Line 15 can be done in
linear time for each element of H (of which there are
O(Q log |V |)). In summary, the overall runtime
of Algo
rithm 1 is O |Q| (|E| log |V | + |V | log2 |V |) .
Remark 1. The last line of Algorithm 1 is intended to
return the best solution found. It may be replaced with
H ∗ ← arg minH|(H,r)∈H W(H), which can only lead to better

solutions. The trouble is that computing W(H) exactly may
be very costly for large H; this poses no difficulty in practice
as the sets found are typically small. However, for the worstcase analysis of the running time bounds, it is important to
use A(H, r) as a proxy for the actual Wiener index W(H).

5.

LOWER BOUNDS

In this section we design methods to prove lower bounds
on the optimal Wiener index. The idea is to have a way
to somehow compare the Wiener index of the solution outputted by our method with the optimum. As the optimal
solution is unknown, we compare against a lower bound on
its cost. While this is pessimistic approach, proving that
our solutions are close to the lower bound allows us to state
with certainty that they are close to optimal as well.
To compute the desired lower bound, we show an integerprogramming formulation of the Min Wiener Connector
problem. Let S denote the vertices in a feasible solution,
i.e., a connector of Q in G. We set a variable yu to 1 for
each u ∈ S (in particular yu = 1 for all u ∈ Q), and another
variable pst for each pair s, t ∈ V (G)×V (G). In the intended
solution, pst = 1 iff ys = yt = 1; we model this by the linear
constraint pst ≥ ys + yt − 1. Notice that the connectivity
requirement is equivalent to being able to route an unit of
st
flow from s to t whenever pst = 1. We add two variables fuv
st
st
and fvu for each edge {u, v} in G and each pair s, t ∈ V ; fuv
which will be set to one when a fixed shortest path from s
to t traverses edges u to v in that direction. For each s, t and
v ∈ V \ {s, t}, the flow
indicate that the net flow
P constraints
st
st
through v is zero:
u∈N (v) [fuv − fvu ] = 0, where N (v) are
the neighbours of v in G. Also, the net flow through
s must
P
st
and
be −pst and for t must be pst . Since dS (s, t) = u,v fuv
P
s,t
st
1
.
the latter sum vanishes when pst = 0, W(S) = 2 u,v fuv
The complete program is shown next.
min

1
2

X

st
fuv

X

st
st
[fuv
− fvu
]

=

u∈N (v)
st
fuv
pst
yu
st , p
fuv
st
yu

min

≤
≥
=
≥
∈



−pst if v = s
pst
if v = t

0
otherwise
yu
ys + yt − 1
1
0
{0, 1}

∀s, t, v ∈ V
∀{u, v} ∈ E
∀s, t ∈ V
∀u ∈ Q

(6)

Theorem 5. Program (6) models the Min Wiener Connector problem.
The proof is reported in Appendix A.5.
Program (6) uses more than 2|E||V |2 variables and more
than |V |3 constraints, which can be problematic for large
graphs. A way to reduce the size of the program is to ask for
minimization of the pairwise sum of distances in the original
graph: this is a safe relaxation as our solutions typically
respect the original distances. Applying this relaxation, the
objective function becomes a linear function of ps,t , thus
eliminating the need for separate flow variables for each s, t
pair and leading to a program significantly smaller in size.
Let yu and pst be
P as before. The Wiener index of any
solution is at least u,v dG (u, v) · puv . To express the condition that the variables with yu = 1 form a connected

1
2

X

dG (s, t) · pst

s,t

X

s.t.

∀v ∈ V \ {q}

xuv

=

yu

[xuv + xvu ]

=

P

[xzi ,zi+1 + xzi+1 ,zi ]

≤

t−1

xuv + xvu
pst
yu
xuv , pst
yu

≤
≥
=
≥
∈

yu
ys + yt − 1
1
0
{0, 1}

u∈N (v)

X

u

yu − 1

{u,v}∈E

X

∀cycle z0 , . . . , zt = z0

i

∀{u, v} ∈ E
∀s, t ∈ V
∀u ∈ Q

(7)

We reduced the number of variables to a more manageable
O(V 2 ), in exchange for exponentially many constraints (one
per cycle in G). This is not a serious issue because the
program above has a separation oracle [27], and commercial
solvers support the addition of lazy constraints [28].

6.

u,v,s,t

s.t.

subgraph, we add two variables xuv and xvu for each edge
(u, v) of G. Pick an arbitrary q ∈ Q and any directed
spanning tree Tq of S rooted at q; the intended solution
will have xuv = 1 if and only if v is the parent of u in
Tq . One constraint is that xuv + xvu ≤ yu : edge (u, v)
can be used only in one direction, and in order to use it
from
P u to v, we must choose u as well. Also, for any u 6= q,
u∈N (v) xuv = yv (any chosen vertex must have exactly one
parent in Tq ). Finally, we need to make sure that the edges
with xuv + xvu = 1 form an undirected tree. A tree with k
vertices hasPk − 1 edges and no
Pcycles; hence we enforce the
constraint u,v [xuv +xvu ] =
yu −1 and, in order to avoid
cycles, we add constraints saying that the sum of xuv + xvu
for all edges (u, v) in every cycle C of G is at most |C| − 1.

EXPERIMENTS

In this section we report the results of our empirical analysis. Here we anticipate the main findings:
• Our approximation algorithm produces solutions which
are close to optimal (§6.2).
• When compared to other concepts of query-dependent
subgraphs extraction such as personalized PageRank
[37] (ppr), Center-piece Subgraph [53] (cps), or the
Cocktail Party Subgraph [48] (ctp), the minimum
Wiener connector is several orders of magnitude smaller
in size, it is much denser, and it includes vertices with
higher centrality (§6.3).
• When the query set Q includes vertices belonging to different communities, ppr, cps, and ctp return solutions
that are 5 to 10 times larger than the case where the
whole of Q belongs to the same community. The minimum Wiener connector is only slightly larger (§6.4).
• Steiner tree produces solutions that are much closer to
the minimum Wiener connector than the other methods. However, in addition to having smaller Wiener index (§6.5), the Steiner-tree solutions are nearly always
less dense, and include vertices with lower centrality.
Also, interestingly, the size of our solutions is comparable to the size of Steiner-tree solutions, despite the fact
that Steiner tree explicitly optimizes for solution size.

cc

ed

0.40
0.62
0.65
0.22
0.14
0.30
0.63
0.63
0.08
0.22
0.28
0.09
0.17
-

3.9
3.8
4.0
8
11
4.4
5
8.2
6.5
3.9
6.5
5.9
5.0
-

Dataset |Q| ws-q

GL

Error interval

3
5
10
20

40
40
40
0
172 172
164
[0, 4.9%]
656 598
538
[9.6%, 22%]
2352 2018 1546† [16.5%, 52.2%† ]

3
5
10
20

16
44
276
1014

16
44
276
964

16
44
260
936

0
0
[0, 6.2%]
[5.1%, 8.4%]

3
5
10
20

36
36
106 106
330 330
1204 1196

36
106
326
1192

0
0
[0, 1.3%]
[0.66%, 1.1%]

3
5
10
20

58
58
58
0
250 250
240
[0, 4.2%]
†
†
1352 1208 1033 [11.9%, 30.9% ]
5490 5490 4032†
[0, 36.2%† ]

Experimental set up

Algorithms. We compare our algorithm ws-q with several
alternative methods described next. Following the literature
on random walks with restart [54, 24, 59], cps is initialized with a restart parameter c=0.85, number of iterations
m=100, and a convergence error threshold ξ=10−7 . To allow cps to converge to the best possible solution, no budget
constraint is given a priori: we greedily add to the solution
the highest-score vertex, until we connect the vertices in Q.
For the personalized PageRank method, ppr, we use the
same settings as cps, as well as the same way of selecting
which and how many vertices to add to the solution.
For ctp [48] we found that the parameter-free version typically returns too large solutions (often with a size comparable to the original graph). In order to limit the size of the
solutions returned while keeping it parameter-free, we first
execute a BFS from each query vertex until all other vertices
in Q are connected, among all these subgraphs we pick the
smallest one, and run over it the greedy algorithm of [48].
For Steiner tree (st) we use the approximation algorithm
by Mehlhorn [41], which is the same that ws-q uses internally to solve the Steiner tree instances it generates (§4).
All algorithms are implemented in C++.
Datasets and query workloads. We use real-world
publicly-available graphs of various types and sizes, spanning different domains: communication over emails and wiki
pages, citation and co-authorship networks, road networks,
social networks, and web graphs (Table 1).
Small datasets are used for assessing approximation quality (§6.2) of our algorithm ws-qw.r.t. the best provable
bounds obtained by solving the integer program in §5.
Medium-large datasets are used for characterizing the solutions produced by the various algorithms described above,
in terms of size, density, and centrality (§6.3).
In all these datasets, the query workloads are made of
random query-sets Q, with controlled size and average distance of the query vertices. Datasets marked with (*) contain ground-truth community structure [58]: these are used
to create different workloads with query vertices in Q belonging to the same community or to different communities
(§6.4). As we delve deeper in the comparison between Min
Wiener Connector and Steiner tree (§6.5), we use benchmarks with predefined query workloads which are used for

GU

football

ad
21.3
55.4
17.9
9.62
5.94
4.12
22.0
6.62
5.27
4.19
17.3
15.1
18.9
-

jazz

δ
9.4e-2
1.4e-1
2.0e-2
8.5e-3
2.6e-3
3.8e-4
1.1e-3
2.1e-5
4.6e-6
1.8e-6
4.3e-6
1.3e-6
1.0e-6
-

6.1

|V |

celegans

|E|

football
115
613
jazz
198
2742
celegans
453
2025
email
1133
5452
yeast
2224
6609
oregon
10670
22002
astro
18772
198110
dblp*
317080
1049866
youtube*
1134890
2987624
wiki
2394385
5021410
livejournal
3997962
34681189
twitter 11316811
85331846
dbpedia 18268992 172183984
puc#
64-4096 448-24574
vienna# 1991-8755 3176-14449

Dataset

Table 2: Comparison of the Wiener index of ws-q’s solution with the lower (GL ) and upper (GU ) bounds found by
Gurobi solver for different datasets and query set sizes. The
cost of the optimal solution is guaranteed to be in [GL , GU ].
†Numbers based on the best lower bound the solver could
prove before it ran out of memory; they give an upper bound
on the error that is likely to be an overestimate.

email

Table 1: Summary of graphs used. δ: density, ad: average degree, cc: clustering coefficient, ed: effective diameter. Datasets with ground truth communities (∗). Classical
Steiner Tree benchmarks with given query workload (#).

assessing Steiner tree algorithms.1 These are marked with
(#) in Table 1: benchmark puc contains 25 problems on
small graphs with |Q| ∈ [8, 2048], while benchmark vienna
contains 85 problems with |Q| ∈ [50, ≈ 5k].
For scalability assessment (§6.6) we use the larger graphs
in Table 1, plus synthetic graphs generated according to the
Erdős-Rényi and Power-Law models.2

6.2

Approximation quality

Table 2 reports the Wiener index of the solution produced by ws-q, and how it compares with the best provable
bounds obtained with the integer-programming formulation
reported in Program (7) (§5) and the state-of-the-art Gurobi
solver [28]. This comparison was carried out on small graphs
as otherwise the number of variables would be too large to
even formulate the integer program. We initialize the solver
with our solution so that the solver’s upper bound can never
be worse by construction. A match in the solver’s upper
and lower bounds indicates an optimal solution was found.
When they do not coincide, either there is a gap between
the best solution and the lower bound from Program (7), or
the solver ran out of memory during the optimization phase
(in which case we report the best lower bound found so far).
We also report an error interval obtained by comparing
our solution with the solver’s best upper and lower bounds.
Observe that, for small query sets (three to five vertices),
ws-q produces solutions that are optimal or very close to it
(with error in the interval [0, 5%]). The worst discrepancy
between our and the solver’s best solution is 16.5% (football
with |Q| = 20); and here all we can prove is that our solution is at most 52.2% from optimal. However, note in this
case there is also a significant gap between the solver’s own
lower and upper bounds, thus 52.2% is likely to be an overestimate. It should also be noted that this query set size is
approximately 1/5 the size of the whole vertex set V .
1
2

http://steinlib.zib.de/
http://snap.stanford.edu/snap/index.html

103

6.4

10

2

|V(H)|

10

bc(H)

δ(H)

104

3

100

10

20

30
|Q|

40

102
101

AD=4

100

50

|Q|=5
1

100

100

10-1

10-1
δ(H)

δ(H)

c
c/s
c
c
c/s ube-d ube-s ube:d
d
:
t
t
t
p
dbl
you
you
you
5.03
8e5 2.3e5 3.5 ctp
11.3 3.6e5 5.0e4 7.4 cps
8.6 3.9e5 4.1e4 9.2 ppr
1.43
20
16 1.3 st
1.38
18
14 1.3 ws-q

104

101

10-2
10-3

2

3

4
AD

5

6

7

4
AD

5

6

7

4

5

6

7

10-2
10-3

10

20

100

30
|Q|

40

50

10-1

1

2

3

1

2

3

100

WS-Q
CTP
CPS
PPR
ST

bc(H)

bc(H)

ctp
cps
ppr
st
ws-q
ctp
cps
ppr
st
ws-q
ctp
cps
ppr
st
ws-q
ctp
cps
ppr
st
ws-q

c

c
c
p-d blp-s
dbl
d
1.4e5 2.8e4
4.1e4 3.69e3
3.4e4 3.5e3
40
29
36
26

with a fixed size of Q, and a fixed average distance among
the vertices in Q, while Figure 3 shows the same statistics
for a single dataset (oregon) with varying size of Q and average distance of the query vertices. Results confirm that
ws-q produces solutions which are always smaller, denser
and contain vertices with higher betweenness centrality than
the other methods. The difference is striking with all the
methods, with Steiner tree being much closer to the type of
solutions produced by ws-q. As expected, since the other
methods do not try to optimize it, ws-q produces solutions
with a Wiener index that is orders of magnitude smaller.
Moreover, the solutions ws-q provides have much smaller
index the Steiner-tree solutions. A deeper comparison between ws-q and st is reported in Section 6.5.

W(H)

|V(H)|

e
tub
st
p
gon
ail
ro
em
yea
ore
ast
dbl
you
671
819
9028
12758
11804
17865
155
188
4556
1735
7349
5615
137
100
1846
598
842
684
26
24
26
26
25
19
24
24
23
23
23
17
0.016 0.016
0.01
<0.01
<0.01
0.01
0.047 0.028
0.02
0.019
0.01
<0.01
0.029 0.039
0.02
0.07
0.01
0.02
0.080 0.088
0.090
0.09
0.08
0.1
0.093 0.091
0.106
0.13
0.11
0.13
<0.01 <0.01
<0.01
<0.01
<0.01
<0.01
0.03
0.02
<0.01
<0.01
<0.01
<0.01
0.03 <0.01
<0.01
0.02
0.01
<0.01
0.09
0.07
0.10
0.11
0.10
0.13
0.11
0.11
0.12
0.14
0.12
0.18
≈ 750k ≈ 2M ≈ 137M ≈ 292M ≈ 400M
≈ 1.5G
54 598 69 296
≈ 50M ≈ 8.3M ≈ 12.6M ≈ 561M
52 222 15 838 ≈ 7.5M
40 079
≈ 1.2M ≈ 1.3M
1 200
1 259
1 164
1 318
3 371
1 324
968
931
923
1 007
2 043
956

Table 4: Average solution size for query workloads based on
ground-truth communities: dc = query vertices in different
communities, sc = query vertices in the same community,
and dc/sc = the ratio of the previous two columns.

|V [H]|

|V [H]|

Table 3: Main characteristics of the solution H returned by
different algorithms on 6 datasets, with |Q| = 10 and average distance of 4 among the vertices in Q. Each experiment
is run 5 times and we report averages of size of the solu
tion |V [H]|, density of the solutions δ(H) = |E[H]|/ |V [H]|
,
2
average betweenness centrality bc(H) of vertices in H, and
Wiener index W(H).

10-2

10-1
10-2

10

20

30

40

50

|Q|

AD

Figure 3: Left column: fixed average distance AD = 4
among query vertices, varying |Q|. Right column: fixed
query set size |Q| = 5, varying average distance among query
vertices. We report |V (H)|, δ(H), and bc(H) on oregon.

6.3

Solution characterization

Table 3 and Figure 3 report a characterization of the solutions produced by the various algorithms in terms of number
of vertices in the solution (|V (H)|), density of the solution
(δ(H)) and betweenness centrality of the vertices in the solution (bc(H)). Table 3 reports results for various graphs

Ground-truth communities workload

Next, we compare the behavior of the various methods
when the query set Q belongs to a community or to multiple communities. To this end, we use graphs with groundtruth community structure (dblp and youtube) and produce
two query workloads for each graph: one with query vertices belonging the same community (denoted sc) and one
with query vertices coming from different communities (denoted dc). Each workload contains 40 queries, 10 for each
size |Q| ∈ {3, 5, 10, 20}. For sc workloads, we pick the community at random, but avoiding small communities (of size
smaller than 100 vertices).
The results are reported in Table 4. We observe that
when Q belongs to multiple communities, random-walkbased methods (ppr and cps) produce solutions which are
from 7 to 11 times larger than when Q belongs to only one
community. While the ratio is less striking for ctp (3 to 5
times larger), the solutions produced are already extremely
large in both workloads.
The results confirm that these methods are conceived to
reconstruct a community around a given seed set of vertices Q, implicitly assumed to belong to the same community; thus, they tend to return significantly larger results
when this does not hold. By contrast, ws-q and st do not
rely on such assumptions, and the difference in average solution size between the two workloads is much smaller.

6.5

Comparison on Steiner tree benchmarks

We have shown that the types of solutions produced by
community-oriented methods have very different characteristics from those by the minimum Wiener connector and the
Steiner tree. We next delve deeper in the comparison between the minimum Wiener connector and the Steiner tree,
using Steiner-tree benchmarks with predefined query workloads, and focusing on the two objective functions of the two
problems: the size of the solution (Steiner) and the sum of
the pairwise shortest-path distances (Wiener).

CDF

CDF

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

vienna
puc
0.9

1
1.1
(a) |V(HST)|/|V(HWSQ)|

1.2

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1.2
1.6
2
(b) W(HST)/W(HWSQ)

2.4

Figure 4: CDFs of the ratio of (a) solution size and (b)
Wiener index on benchmarks vienna and puc.
Figure 4 reports the cumulative distribution functions
(CDFs) of the ratio of solution size (left) and Wiener index (right) between st and ws-q, on the two benchmarks
puc and vienna. As expected, ws-q produces solutions which
have a much smaller sum of the pairwise shortest-path distances. Also interesting to observe is the fact that our algorithm ws-q often outperforms the well-established Steinertree approximation-algorithm by Mehlhorn [41] with respect
to the size of the solution, which is the objective function of
the Steiner tree (recall that the Min Wiener Connector
objective function implicitly favors small solutions).
Interestingly, we also observe that many problem instances on the vienna benchmark are real-world instances
of the situation depicted earlier in Figure 2 – that is to say
ws-q produces a slightly larger solution in number of vertices, yet with a significantly smaller Wiener index.

6.6

cancer

cancer/alzheimers

cancer

p53

HSP90

alzheimers

GSK3B

SNCA

PSEN

alzheimers

neurodegenerative

BMP1

Scalability

We now focus on ws-q’s runtime performance and scalability with an increasing graph or query set size. We use
Erdős-Rényi (ER) and Power-Law (P L) models to generate
synthetic graphs with varying size, while keeping constant
other graph properties. We also use the larger real-world
graphs in Table 1. Results are reported in Figure 5. First,
we note that the performance of the algorithm is not significantly affected by the type of graph (random or power-law).
Second, runtime has an almost linear relationship with the
query set size, as well as the input graph size. However, as
expected by Theorem 4, runtime is most impacted by the
graph size rather than the query-set size.
Parallelization. Examining Algorithm 1 we notice that
we can easily speed-up our method via parallelization (e.g.,
via a Map-Reduce execution), assuming the graph G fits in
memory. In fact, by launching |Q| threads in parallel (Map),
we can achieve a linear speedup of |Q|. Each thread examines one root r ∈ Q and computes shortest-path distances
in G from r to construct and solve the Steiner tree instances
for different choices of the parameter λ. Then, all possible solutions can be collected (Reduce), and the best one
chosen. To this end, each thread needs to evaluate its candidate solutions. Since these are typically small in practice,
the thread can compute the induced shortest-path distances
from all vertices in its solutions and compute their Wiener
indices exactly. In the (unlikely) scenario that a solution is
large, we can instead approximate the Wiener index (see Remark 1). This preserves the approximation guarantee while
providing an overall speedup of |Q|. If G is too large to
fit in memory, it becomes necessary to employ techniques
for parallel and/or approximate shortest-distance computations [52, 4, 40, 45], but these are beyond the scope of this
work.

JAK2
leukemia

autism

SLC6A

Figure 6: A minimum Wiener connector extracted from a
PPI network and links genes associated with cancer and
Alzheimer’s disease.

7.

CASE STUDIES

Protein-Protein-Interaction network. Network analysis has established itself as a central component of computational and systems biology. Barabasi et al [5] drew attention
to the great potential of “network medicine” in the study
of diseases. This work highlighted the utility of identifying not only vertices with high betweenness centrality, but
also those that act as links between diseases. Finding such
vertices may lead to the discovery of new protein-disease associations and a deeper understanding of the relationships
between diseases [13, 12, 47, 7].
The minimum Wiener connector fits well in this setting,
as it aims at finding few central vertices that connect a
given set of query vertices. As a proof of concept we use a
human Protein-Protein-Interaction (PPI) network collected
from BioGrid3 with 15 312 vertices. To demonstrate the utility of ws-q we require a ground truth about the relationship,
so we select query proteins that have been the subject of previous biological study. In Figure 6 we report the minimum
Wiener connector for a query set shown in grey, and the solution connector-vertices in white. For each query node we
analyze the disease-association of its next-hop in the connector, and find that it is indicative of the studied association of
the query node. For example, we observe that the next-hop
of BMP1 is p53 which is widely regarded as central in cancer; we then verify in the literature that in fact BMP1 has
also been linked to cancer [55, 51]. Similar literature-verified
examples are:
• PSEN is related to the other query nodes through
GSK3B – uncovering its role in Alzheimer’s disease.
• JAK2 is connected through HSP90 which has been
studied for its potential therapeutic role in JAK-related
diseases [6, 23].
• SLC6A4 is suspected to play a role in Alzheimer disease, and is connected to SNCA, a known factor in
Alzheimer’s.
Further, the high connectivity of the inner nodes insinuates
a close relationship between Cancer and Alzheimer’s (e.g.,
as seen by the interaction between p53 and GSK3B ), which
has in fact been a topic of interest and study [44, 32, 25].
This sample query is exemplary of the quality and potential of finding the minimum Wiener connector. Identifying
not only high betweenness and important nodes, but also
those that act as links, gives potential for new directions
of investigation for protein-disease and disease-disease relationships. The connector also provides a concise summary
of the relationships that is amenable to visualization.
Social network. The next case study is based on a graph
created over Twitter users taking part in the ACM SIGKDD
2014 conference. The graph contains 1 141 Twitter users
whose tweets over the three-day period contained the hash3

http://thebiogrid.org/

105
104

104

PL, |V|=10k
PL, |V|=100k

ER, |V|=10k
ER, |V|=100k

Runtime (s)

Runtime (s)

103
102
101
100

PL, |Q|=10
PL, |Q|=100

ER, |Q|=10
ER, |Q|=100

103
102
101
100
10-1

10-1 0
10

101

102

10-2

103

103

104

|Q|
105
10

104

wiki
livejournal

yeast
oregon

4

Runtime (s)

10
Runtime (s)

106

102
101
100

livejournal

|Q|=3
|Q|=5
|Q|=10

103

3

102
101

email
yeast

0

10

oregon
astro

wiki
dblp

twitter
dbpedia

youtube

-1

10

10-1

10-2

-2

10

-3

10

105
|V|

1

10
|Q|

100

10-3

103

104

105
|V|

106

107

Figure 5: Computational runtime of ws-q on different synthetic Power-Law (P L) and Erdős-Rényi (ER) graphs (first row)
and real-world graphs (second row), with varying query set size and fixed graph size (left column), and varying graph size
and fixed query set size (right column).
data_nerd
G7

cornell_tech
G10

jonkleinberg
G13

destrin
G10

irescuapp
G10

kdnuggets
G1

UserId

kdnuggets
G1

drewconway
G4

jromich
G11

thrillscience
G11

Figure 7: Two minimum Wiener connectors extracted from
the Twitter #kdd2014 graph.
tag #kdd2014, or who replied to or were mentioned in these
tweets. There is an edge between two users for each reply or
mention. The Clauset-Newman-Moore algorithm was used
to cluster the graph into 10 communities.4
Figure 7 reports two minimum Wiener connectors extracted with query sets Q (shown in gray) consisting of
vertices belonging to different communities. The vertices
chosen to be combined with Q to produce the solution subgraph H are, in both cases, users that exhibit some influence
or leadership. In particular, we observe that in both examples, H contains the users kdnuggets and drewconway, each
of which have a very large set of Twitter followers (23.1k and
10k respectively), and turn out to be the top mentioned and
replied-to users in the whole #kdd2014 dataset. Table 5
contains more detailed information. In particular it shows
that the other intermediate vertices included in the minimum Wiener connectors also exhibit high levels of activity
and are among the top-10 mentioned or replied-to users in
their respective communities.
4

Followers

Notes

kdnuggets

gizmonaut
G13

irescuapp
G10

francescobonchi
G2

drewconway
G4

Table 5: Statistics on Tweeters in #kdd2014 graph.

nicola_barbieri
G2

https://nodexlgraphgallery.org/Pages/Graph.aspx?graphID=26533

23.1k Top-1 mentioned in entire graph & G1
Top-1 betweenness in entire graph
Top-3 word in entire graph & G1
Top-6 mentioned in G2-G8
Top-10 word in G4
Top-2 replied-to in G8
drewconway
10.7k Top-7 mentioned in entire graph & G1, G4
Top-4 replied-to in entire graph & G2, G3
Top-6 word in G4
gizmonaut
304 Top-9 tweeter in G10
irescuapp
204 Top-7 mentioned in G10
jromich
165 Top-7 replied-to in G1
f rancescobonchi 619 Top-7 mentioned in G2

8.

CONCLUSIONS

In this paper we introduced the Min Wiener Connector problem: given a graph and a set of query vertices, find
a subgraph that connects the query vertices while minimizing the sum of pairwise shortest-path distances within that
subgraph. In such simple and elegant formulation, the objective function favors small solutions built by adding important (central) vertices to connect the given query vertices.
Thanks to these features, the minimum Wiener connector
lends itself naturally to applications in biological and social
network analysis.
We showed that the problem is NP-hard, cannot admit
any PTAS, and has an exact (yet impractical) algorithm that
runs in polynomial time for the special case where the size
of the query set is constant. Also, as a major contribution,
we provided a constant-factor approximation algorithm that
runs in time proportional (up to logarithmic factors) to the
size of the input graph and the number of query vertices.

9.

REFERENCES

[1] R. Andersen, F. R. K. Chung, and K. J. Lang. Local
graph partitioning using PageRank vectors. In FOCS
2006.
[2] R. Andersen and K. J. Lang. Communities from seed
sets. In WWW 2006.
[3] S. Asur and S. Parthasarathy. A viewpoint-based
approach for interaction graph analysis. In KDD 2009.
[4] D. Bader and K. Madduri. Parallel algorithms for
evaluating centrality indices in real-world networks. In
Int. Conf. on Parallel Processing, pages 539–550, 2006.
[5] A.-L. Barabási, N. Gulbahce, and J. Loscalzo. Network
medicine: a network-based approach to human
disease. Nature Reviews Genetics, 12(1):56–68, 2011.
[6] J. Bareng, I. Jilani, M. Gorre, H. Kantarjian, F. J.
Giles, A. Hannah, and M. Albitar. A potential role for
HSP90 inhibitors in the treatment of JAK2
mutant-positive diseases as demonstrated using
quantitative flow cytometry. Leukemia & lymphoma,
48(11):2189–2195, 2007.
[7] A. Baryshnikova, M. Costanzo, C. L. Myers,
B. Andrews, and C. Boone. Genetic interaction
networks: toward an understanding of heritability.
Annual review of genomics and human genetics,
14:111–133, 2013.
[8] A. Bavelas. A mathematical model of group structure.
Human Organizations, 7:16–30, 1948.
[9] R. Burt. Structural Holes: The Social Structure of
Competition. Harvard University Press, 1992.
[10] J. Byrka, F. Grandoni, T. Rothvoss, and L. Sanità.
Steiner tree approximation via iterative randomized
rounding. J. ACM, 60(1):6:1–6:33, Feb. 2013.
[11] E. Çela, N. S. Schmuck, S. Wimer, and G. J.
Woeginger. The Wiener maximum quadratic
assignment problem. Discret. Optim., 8(3):411–416,
2011.
[12] S. Chandrasekaran and D. Bonchev. A network view
on Parkinson’s disease. Computational and structural
biotechnology journal, 7(8):1–18, 2013.
[13] X. Chang, T. Xu, Y. Li, and K. Wang. Dynamic
modular architecture of protein-protein interaction
networks beyond the dichotomy of ’date’ and ’party’
hubs. Scientific reports, 3, 2013.
[14] W. Cui, Y. Xiao, H. Wang, Y. Lu, and W. Wang.
Online search of overlapping communities. In
SIGMOD, pages 277–288, 2013.
[15] W. Cui, Y. Xiao, H. Wang, and W. Wang. Local
search of communities in large graphs. In SIGMOD,
pages 991–1002, 2014.
[16] M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn,
F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM J. Comput., 23(4):738–761, 1994.
[17] I. Dinur and S. Safra. On the hardness of
approximating minimum vertex cover. Annals of
Mathematics, 162(1):439–485, 2005.
[18] A. Dobrynin, R. Entringer, and I. Gutman. Wiener
index of trees: Theory and applications. Acta
Applicandae Mathematica, 66(3):211–249, 2001.
[19] C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast
discovery of connection subgraphs. In KDD, 2004.

[20] J. Fink, B. Lužar, and R. Škrekovski. Some remarks
on inverse Wiener index problem. Discrete Appl.
Math., 160:1851–1858, 2012.
[21] M. Fischermann, A. Hoffmann, D. Rautenbach,
L. Székely, and L. Volkmann. Wiener index versus
maximum degree in trees. Discrete Appl. Math.,
122(1–3):127–137, 2002.
[22] D. S. R. Frank K. Hwang and P. Winter, editors. The
Steiner Tree Problem. Annals of Discrete
Mathematics. Elsevier, 1992.
[23] J. S. Fridman and N. J. Sarlis. The interplay between
inhibition of JAK2 and HSP90. JAK-STAT,
1(2):77–79, 2012.
[24] Y. Fujiwara, M. Nakatsuji, M. Onizuka, and
M. Kitsuregawa. Fast and exact top-k search for
random walk with restart. Proc. VLDB Endow.,
5(5):442–453, 2012.
[25] C. Gao, C. Hölscher, Y. Liu, and L. Li. Gsk3: a key
target for the development of novel treatments for
type 2 diabetes mellitus and Alzheimer disease.
Reviews in the Neurosciences, 23(1):1–11, 2012.
[26] M. Girvan and M. E. J. Newman. Community
structure in social and biological networks. National
Academy of Sciences of USA, 99(12):7821–7826, June
2002.
[27] M. Grötschel, L. Lovász, and A. Schrijver. The
ellipsoid method and its consequences in combinatorial
optimization. Combinatorica, 1(2):169–197, 1981.
[28] Gurobi Optimization, Inc. Gurobi optimizer reference
manual, 2015.
[29] T. H. Haveliwala. Topic-sensitive pagerank. In WWW
2002.
[30] T. C. Hu. Optimum communication spanning trees.
SIAM J. Comput., 3(3):188–195, 1974.
[31] X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu.
Querying k-truss community in large and dynamic
graphs. In SIGMOD, pages 1311–1322, 2014.
[32] K. M. Jacobs, S. R. Bhave, D. J. Ferraro, J. J. Jaboin,
D. E. Hallahan, and D. Thotala. GSK-3: A
bifunctional role in cell death pathways. International
journal of cell biology, 2012, 2012.
[33] G. Jeh and J. Widom. Scaling personalized web
search. In WWW 2003.
[34] D. Kempe, J. M. Kleinberg, and É. Tardos.
Maximizing the spread of influence through a social
network. In KDD, 2003.
[35] S. Khuller, B. Raghavachari, and N. E. Young.
Balancing minimum spanning trees and shortest-path
trees. Algorithmica, 14(4):305–321, 1995.
[36] P. Klein and R. Ravi. A nearly best-possible
approximation algorithm for node-weighted Steiner
trees. Journal of Algorithms, 19(1):104–115, July 1995.
[37] I. M. Kloumann and J. M. Kleinberg. Community
membership identification from small seed sets. In
KDD 2014.
[38] Y. Koren, S. C. North, and C. Volinsky. Measuring
and extracting proximity graphs in networks. TKDD,
1(3), 2007.
[39] G. Kossinets and D. J. Watts. Empirical analysis of an
evolving social network. Science, 311(5757):88–90,
2006.

[40] N. Kourtellis, T. Alahakoon, R. Simha, A. Iamnitchi,
and R. Tripathi. Identifying high betweenness
centrality nodes in large social networks. Social
Network Analysis and Mining, 3:899–914, 2013.
[41] K. Mehlhorn. A faster approximation algorithm for
the Steiner problem in graphs. Inf. Proc. Letters,
27(3):125–128, 1988.
[42] B. Mohar and T. Pisanski. How to compute the
Wiener index of a graph. J. Mathematical Chemistry,
2(3):267–277, 1988.
[43] R. Pagh and F. F. Rodler. Cuckoo hashing. J.
Algorithms, 51(2):122–144, 2004.
[44] C. J. Proctor and D. A. Gray. GSK3 and p53-is there
a link in Alzheimer’s disease? 2010.
[45] M. Riondato and E. M. Kornaropoulos. Fast
Approximation of Betweenness Centrality Through
Sampling. In WSDM, 2014.
[46] P. Rozenshtein, A. Anagnostopoulos, A. Gionis, and
N. Tatti. Event detection in activity networks. In
KDD, pages 1176–1185, 2014.
[47] J. A. Santiago and J. A. Potashkin. A network
approach to clinical intervention in neurodegenerative
diseases. Trends in Molecular Medicine, 20(12):694 –
703, 2014.
[48] M. Sozio and A. Gionis. The community-search
problem and how to plan a successful cocktail party.
In KDD, pages 939–948, 2010.
[49] D. A. Spielman and S. Teng. Nearly-linear time
algorithms for graph partitioning, graph sparsification,
and solving linear systems. In STOC 2004.
[50] D. Stefanovic. Maximizing Wiener index of graphs
with fixed maximum degree. MATCH Commun. Math.
Comput. Chem., 60:71–83, 2008.
[51] J. P. Thawani, A. C. Wang, K. D. Than, C.-Y. Lin,
F. La Marca, and P. Park. Bone morphogenetic
proteins and cancer: review of the literature.
Neurosurgery, 66(2):233–246, 2010.
[52] M. Thorup and U. Zwick. Approximate distance
oracles. J. ACM, 52(1):1–24, 2005.
[53] H. Tong and C. Faloutsos. Center-piece subgraphs:
problem definition and fast solutions. In KDD, pages
404–413, 2006.
[54] H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random
walk with restart and its applications. In ICDM, pages
613–622, 2006.
[55] B. Vogelstein, S. Sur, and C. Prives. p53: the most
frequently altered gene in human cancers. Nature
Education, 3(9):6, 2010.
[56] H. Wang. The extremal values of the Wiener index of
a tree with given degree sequence. Discrete Appl.
Math., 156(14):2647–2654, 2008.
[57] H. Wiener. Structural determination of paraffin
boiling points. J. Am. Chem. Soc, 69(1):17–20, 1947.
[58] J. Yang and J. Leskovec. Defining and evaluating
network communities based on ground-truth. Knowl.
Inf. Syst., 42(1):181–213, 2015.
[59] A. W. Yu, N. Mamoulis, and H. Su. Reverse top-k
search using random walk with restart. Proc. VLDB
Endow., 7(5):401–412, 2014.
[60] W. Zachary. An information flow model for conflict
and fission in small groups. J. Anthropol. Res.,
33(4):452–473, 1977.

[61] X.-D. Zhang and Q.-Y. Xiang. The Wiener index of
trees with given degree sequences. MATCH Commun.
Math. Comput. Chem., 60:623–644, 2008.

APPENDIX
A.
A.1

REMAINING PROOFS
Proof of Theorem 3 (Section 3)

Recall that a homomorphism between two graphs H
and H 0 is a mapping φ : V (H) → V (H 0 ) such that (u, v) ∈
E(H) implies (φ(u), φ(v)) ∈ E(H 0 ).
Lemma 6. Let φ : H → H be a surjective graph homomorphism. Then W(H 0 ) ≤ W(H).
Proof. The existence of a homomorphism implies that
for every path p in H, there is a corresponding path in
H 0 (which may not be simple even if p is). Therefore
dH 0 (φ(u), φ(v)) ≤ dH (u, v), and
X
W(H) =
dH (u, v)
u,v∈V (H)

≥

X

dH 0 (φ(u), φ(v))

u,v∈V (H)

≥

X

dH 0 (u0 , v 0 )

u0 ,v 0 ∈φ(V (H))

=

X
u0 ,v 0 ∈V

dH 0 (u0 , v 0 ).

(H 0 )

The second inequality uses the fact that every pair u0 , v 0
from the image of V (H) under φ is counted at least once as
dH 0 (φ(u), φ(v)) for some u, v ∈ V (H). The last equality is
by the surjectivity of φ.
Lemma 7. Let G be a graph, H be a connected subgraph
of G, Q ⊆ V (H) and let
A = Q ∪ {v ∈ V (H) | degH (v) > 2}.
We call A the set of pivotal vertices of H with respect to Q.
Call a path p between two vertices of A basic if the internal
vertices of p are outside A; say that an unordered pair of
vertices u, v ∈ A is neighbouring if u, v ∈ V (H) and there
is a basic path from u to v. Suppose we construct a graph H 0
by including the vertices and edges of an arbitrary shortest
path in G between each pair of neighbouring elements of A.
Then Q ⊆ V (H 0 ) and either W(H 0 ) = W(H), or H is not
a minimum Wiener connector for Q.
Proof. It suffices to show that if H is a minimum Wiener
connector for Q, then we can construct a surjective homomorphism φ from H to H 0 whose restriction to A is the identity. Indeed, then clearly Q ⊆ A ⊆ V (H 0 ), and Lemma 6
would imply W(H 0 ) ≤ W(H).
For each neighbouring pair (u, v) ∈ A×A, there is a unique
basic path p = p0 . . . pt in H between u = p0 and v = pt
(otherwise removing some path yields a smaller connector).
The graph H 0 contains a path q0 , . . . , qt0 in G (where t0 ≤ t);
define φ(pi ) = qmin(i,t0 ) for i ∈ {0, . . . , t0 }. The map φ is
well-defined because the internal vertices of all these paths
in H are distinct, as their degree is 2. By construction, φ is
surjective on V (H 0 ) and φ(u) = u for all u ∈ A. Moreover,
the image of every edge in the unique basic path between

a pair of neighbouring vertices is an edge of H 0 . Since any
edge of H must belong to some basic path (or else we could
remove one of its endpoints while reducing the Wiener index
of H), it follows that φ is a homomorphism, as claimed.

A.2

Proof of Lemma 1 (Section 4)

P
Let r∗ = argminr v dH (v, r). Observe that
X
X X

|V (H)| ·
dH (v, r∗ ) =
dH (v, r∗ )
v

Lemma 8. Let H be a connected graph and let P =
({si , ti })i∈[m] denote a sequence S
of m unordered pairs of distinct vertices of H. Write T = i∈[m] {si , ti } and call a sequence p1 , . . . , pm of paths in H valid if for all i ∈ [m], pi
is a shortest path between si and ti . There is a valid sequenceSp1 , . . . , pm of paths in H such that in the subgraph
H 0 = i∈[m] pi of H there are at most m(m − 1) vertices
with degree different from two, and W(H 0 ) ≤ W(H).
Proof. Since H is connected, there is some valid sequence of paths; what we need to show is that there is one
with the degree property. We argue by induction on m.
When m = 1, all the internal vertices of any shortest pair
between s1 and t1 have degree two, so we are done. Suppose
the theorem holds for m − 1 vertex pairs; let p1 , . . . , pm−1
be the paths in the conclusion of the lemma, and take an
arbitrary shortest path pm from sm to tm . We claim that
we can replace the path pm with another path p0m such that,
for each pi with i < m, at most two vertices have a different
successor or predecessor in the two paths p0m and pi . This is
easy to see because if pm meets pj , leaves it and intersects
it for a second time, we can replace the part of pm between
the two intersections by a subpath of pj .
Consequently,
when we add the edges in path p0m to the
S
subgraph i∈[m−1] pi , for any i < m we increase the degree
of at most two vertices that belong to pi . Therefore the
total number of vertices of degree larger than two is at most
(m − 1)(m − 2) + 2(m − 1) = m(m − 1), as desired.
Finally, note that the above path-replacement procedure
cannot increase the Wiener index as H 0 is a subgraph of H
that maintains shortest-path distances.
Lemma 9. Let k = |Q|. For any graph G, there is an
optimal solution to Min Wiener Connector where at most
k4 vertices have degree in H larger than two.
Note that such H is not necessarily an induced subgraph.
Proof. Let H be an optimal solution. Consider a sequence P containing all m = k2 pairs of distinct query
nodes. By Lemma 8, there is a sequence p1 , . . . , pm of shortest paths in H (one for each pair of query nodes) such that
in the graph H 0 formed by the union of all these paths, there
are most m(m − 1) vertices with degree different from two.
Clearly H 0 is a connector for Q (since it contains paths linking each pair of query nodes). Since W(H 0 ) ≤ W(H) and H
is optimal, it follows that W(H 0 ) = W(H). Also, there cannot be any non-query vertices of degree 1, otherwise we could
remove them from H 0 and still obtain a connector of Q with
smaller Wiener index. So the total number of vertices of
degree larger than 2 in H 0 is at most k + m(m − 1) ≤ k4 .
Proof of Theorem
3. Let k = |Q|. We can loop over

all possible kn4 vertex subsets of size k4 ; by Lemma 9 one
of them will be the set X of vertices of degree 2 in the
optimal solution H ∗ . Then X∪Q is the set of pivotal vertices
of H ∗ with respect to Q; we can construct in polynomial
time a graph H 0 as in Lemma 7, and we will have W(H 0 ) ≤
W(H ∗ ), hence W(H ∗ ) = W (H 0 ).
Overall, the algorithm runs in time npoly(k) .

w

≤

v

X X

dH (v, w)



= 2 W(H),

v
X X w

and 2 W(H) ≤
[dH (v, r∗ ) + dH (r∗ , w)]
w

=

X

v

dH (v, r∗ ) +

v,w

=2

X

X

dH (r∗ , w)

v,w
∗

dH (v, r ) = 2 |V (H)| ·

v,w

X

dH (v, r∗ ),

v

where we used the choice of r∗ in the first inequality and the
triangle inequality for dH in the second inequality.

A.3

Proof of Lemma 2 (Section 4)

Let TS be the shortest-path tree from r to the elements
of T , determined by an array of distances dS [] and an array
of parent links pS []. Consider the algorithm below, which
traverses T and performs a series of edge relaxations that
add additional vertices from TS in order to decrease distances to the root r. The important invariant maintained
is that the edges {(p[v], v)} | d[v] 6= ∞} form a subtree of
T ∪ TS , with d[v] an upper bound on the distance between
the root and v in the tree.
Algorithm 2 AdjustDistances
Input: A graph G = (V, E); a subtree T ; a root node v ∈ V (T );
and a BFS tree from r with parent array pS [] and distance
array dS [].
Output: A tree.

1: Construct hash tables d[], p[], with default values p[v] = nil
and d[v] = ∞ for all v ∈ V (G).

2: d[r] ← 0.
3: dfs(r).
4: return the tree T 0 = {(v, p[v]) | v ∈ V (G) ∧ p[v] 6= nil}.

Algorithm 3 dfs
Input: A vertex u.
√
1: if d[u] > (1 + 2)dS [u] then
2:
AddPath(u)
3: end if
4: for each child v of u in T do
5:
relax(u, v)
6:
dfs(v)
7:
relax(v, u)
8: end for

Algorithm 4 AddPath
Input: A vertex u.
1: v ← u
2: while d[v] > dS [v] do
3:
relax(pS [v], v)
4:
v ← p[v]
5: end while

We need to show that AdjustDistances runs in time
O(|V (T )|) and returns a tree T 0 satisfying the following:
(a) V (T 0 ) ⊇ V (T );

Algorithm 5 Relax

P
Hence v∈V (T 0 )\V (T ) dG (v) ≤
implies c).

Input: two adjacent vertices u, v.
1: if d[v] > d[u] + 1 then
2:
d[v] ← d[u] + 1
3:
p[v] ← u
4: end if

A.4

1√
1+ 2

P

v∈V (T )

Proof of Lemma 3 (Section 4)

We need the following lemma.
Lemma 10. Let x0 , y0 ∈ R+ and λ =

√
(b) |V (T 0 )| ≤ (1 + 2)|V (T )|;

dG (v), which

+

x, y ∈ R
√

(c) for all v ∈ V (T 0 ), dT 0 (r, v) ≤ (1 + 2) dG (r, v).
√ P
P
(d)
2 v∈V (T ) dG (r, v).
v∈V (T 0 ) dG (r, v) ≤
Property a) holds because every time we insert a new vertex u in the tree (that is, p[u] becomes 6= nil), it is never removed again; and the call dfs(r) visits all vertices of T . Prop0
erty c) holds because d[u] =
√ dS [u] for all u ∈ V (T ) \ V (T ),
and whenever d[u] > (1 + 2)dS [u] for some u ∈ V (T ), we
add a path to achieve d[u] = dS [u].
Next we analyze the running time. For d[] and p[] we
use a resizable hash table with constant expected amortized
update/lookup time [16, 43]. When an element v is not in
the table, we insert p[v] ← nil and d[v] ← ∞. This way lines
1-2 of AdjustDistances take time O(1). We also keep track of
which elements v ∈ V (G) have been assigned values in the
table, so line 4 takes time O(|V (T 0 )|) rather than O(|V (G)|).
The running time of dfs(r) (excluding line 1, which is run
O(|V (T )|) times) is proportional to the number of calls to
relax made by AddPath and the recursive calls to dfs. The
number of relaxations is O(|V (T 0 )|) because every edge of T
or TS is relaxed at most twice by dfs and at most once by
AddPath. Therefore the running time of dfs(r) is O(|V (T 0 )|),
which is also O(|V (T )|) assuming property b).
Now we show property b). As the algorithm executes, define a potential function Φ to be the distance estimate of the
current vertex (for ease of notation we omit the dependence
of Φ on the current time). When a shortest path of length
` = dS [u] to the current vertex√u is added by AddPath(u),
φ = d[u] > α`, where α = 1 + 2. Adding the path lowers
d[u] to `, decreasing φ by at least (α − 1)`. Hence the total length of the added paths is bounded by the sum of the
decrements to φ during the course of the algorithm, divided
by α − 1. Since φ is initially 0 and always nonnegative,
the sum of the decreases is at most the sum of the increments. The potential Φ increases only when the current
vertex changes from some vertex u to a vertex v after the
edge (u, v) was relaxed, which ensures that d[v] ≤ d[u] + 1
and that Φ increases by at most 1. Since each edge is traversed twice, the total of the increases to Φ during the course
of the algorithm is bounded by twice the number of edges
in T . This establishes that the √
total length of the added
times the total number
paths is bounded by 2/(α − 1) = 2 √
of edges of T . Thus, |V (T 0 )| ≤ (1 + 2)|V (T )|, showing b).
Only property d) remains to be shown. Define analogously

a potential Ψ to be d[v]+1
when the current vertex is v ∈
2
V (T ). Adding a shortest path of length
` when d[v] > (1 +
√
√
2)` lowers Ψ by at least `2 (1 + 2). The vertices
 added
increase the sum of distances from r by at most `−1
≤ `2 /2.
2
Hence the total increase in sum of distances is bounded
by
√
the sum of the decrements to Ψ, divided by 2(1 + 2). The
sum of the deceases is at most the sum of the increases.
The potential Ψ increases by at most dG (v) when relaxing
an edge (u, v). Since each edge is traversed P
twice, the total
of the increases to Ψ is bounded by 2(1+2√2) v∈V (T ) dG (v).

q

y0
.
x0

Then, for all

it holds that



xλ + λy 2
xy
≤
.
x0 y0
x0 λ + yλ0
Proof. Our choice of λ implies that 4x0 y√
=
0
2
x0 λ + yλ0 . Recall that, by the AM–GM inequality, ab ≤
a+b
⇒ 4ab ≤ (a + b)2 for all a, b ∈ R+ . Hence
2



4 (xλ) λy
xλ + λy 2
xy
4xy
=
=
.
≤

2
x0 y0
4x0 y0
x0 λ + yλ0
x0 λ + y0
λ

∗
Now we are ready to show Lemma 3. Let
denote the
qA
P
u∈A∗ dG (r,u)
.
optimal solution to Problem 3 and set λ =
|A∗ |
√ p
It is easy to see that λ ∈ [1/ 2, |V (G)|] as all distances
dG (r, u) but one (i.e., dG (r, u) which is equal to 0) are in
the range [1, |V (G)|] and |A∗ | ≥ 2. Let B ∗ (resp., B) denote
the optimal solution (resp., an α-approximate solution) to
Problem 4. By our choice of λ, Lemma 10 implies that
P
e
|B| u∈B dG (r, u)
A(B,
r)
P
= ∗
e ∗ , r)
|A | u∈A∗ dG (r, u)
A(A
!2
P
|B|λ + λ1 u∈B dG (r, u)
P
≤
|A∗ |λ + λ1 u∈A∗ dG (r, u)

2

2
B(B, r)
B(B, r)
=
≤
,
B(A∗ , r)
B(B ∗ , r)

where the last inequality follows from B(A∗ , r) ≥ B(B ∗ , r)
(due to the optimality of B ∗ for Problem 4). To complete
B(B,r)
the proof, note that B(B
∗ ,r) ≤ α holds by hypothesis.

A.5

Proof of Theorem 5 (Section 5)

We have to show that an optimal solution to (6) gives an
optimal solution to our problem, and viceversa.
It is clear that any solution S ⊆ V (G) to Min Wiener
Connector yields a feasible solution to (6): set yu = 1
and puv = 1 iff u, v ∈ S, and for each s, t ∈ S, pick a
shortest path z0 = s, z1 , . . . , zt = t from s to t in S and set
fzsti ,zi+1 = 1; set all other variables to 0. This satisfies all
constraints and the objective function coincides with W(S).
Conversely, consider an optimal solution to (6) and let
S = {u ∈ V | yu = 1}; note that S ⊇ Q. We show that
the objective function is at least W(G[S]). For any s, t ∈ S,
pst ≥ ys +yt −1 ≥ 1. The constraints now imply that we can
route pst ≥ 1 units of flow from s to t, where the capacity
of directed edge (u, v) is at most yu . Note that once yu
and pst have been fixed, all remaining constraints involve
only flow variables and constants, and only flow variables
with the same pair s, t. Therefore, the only way to minimize
the objective function is to find, for each s, t, a min-cost
flow of value pst (where the cost and capacity of every edge
is one), i.e., a shortest-path from s to t in S. Thus there
st
is such a path p, and the sum of fuv
for the directed edges
(u, v) of p is at least dS (s, t). As this holds for all s, t, the
result follows.

