Graphs with Connected Medians.
The median set of a graph G with weighted vertices comprises the vertices minimizing the average weighted distance to the vertices of G. We characterize the graphs in which, with respect to any nonnegative vertex weights, median sets always induce connected subgraphs. The characteristic conditions can be tested in polynomial time (by employing linear programming) and are immediately verified for a number of specific graph classes.
Introduction
. Given a (finite, connected) graph G one is sometimes interested in
finding the vertices minimizing the total distance
to the vertices u of G; where the distance d(u; x) between u and x is the length of a shortest
path connecting u and x: The subgraph induced by all minima of F need not be connected:
actually every (possibly disconnected) graph can be realized as such a "median" subgraph of
another graph (Slater [23]); see Hendry [18] for further information and pertinent references.
Here we will focus on the weighted version of the median problem, which arises with one of
the basic models in discrete facility location [25] and with majority consensus in classification
and data analysis [3, 9, 10, 11, 22]. A weight function is any mapping - from the vertex set to
the non-negative real numbers, which is not the zero function (in order to avoid trivialities).
The total weighted distance of a vertex x in G is given by
A vertex x minimizing this expression is a median (vertex) of G with respect to -; and the
set of all medians is the median set Med(-): By a local median one means a vertex x such
that F - (x) does not exceed F - (y) for any neighbour y of x: Denote by Med loc
(-) the set of
all local medians. We will consider the following questions:
Research supported in part by the Alexander von Humboldt Stiftung
ffl When are all median sets Med(-) of a graph connected?
ffl When does Med loc
(-) hold for all weight functions - ?
If we allow only 0-1 weight functions -; then recognition of graphs with Med loc
is an NP -complete problem [2]. We will show that connectivity of median sets with respect
to arbitrary weight functions turns out to be equivalent to the condition that for each function
F - all local minima are global. This property can also be formulated as a certain convexity
condition.
In the next section we investigate weakly convex functions on graphs, and in Section 3
we then obtain the basic characterizations of graphs with connected medians. One of those
equivalent conditions, weak convexity of F - for each weight function -, can be formulated
as a linear programming problem, thus allowing to recognize graphs with connected medians
in polynomial time. This LP condition, however, entails a lot of redundancy and cannot
be read off from other graph properties, which are known to imply median connectedness.
Striving for less redundancy in the requirements, we establish the main result in Section 4 by
employing LP duality to a particular instance of the original LP formulation. This theorem
can conveniently be used to derive median properties in several specific classes of graphs, as
is demonstrated in the final section.
2. Weakly convex functions. A real-valued function f defined on the vertex set V
of a graph G is said to be weakly convex if for any two vertices u; v; and a real number -
between 0 and 1 such that -d(u; v) and (1 \Gamma -)d(u; v) are integers, there exists a vertex x
such that
Weakly convex functions were introduced by Arkhipova and Sergienko [1] under the name
"r-convex functions"; see also Lebedeva, Sergienko, and Soltan [19].
The interval I(u; v) between two vertices u and v consists of all vertices on shortest
u; v-paths, that is:
For convenience we will use the short-hand
I
to denote the "interior" of the interval between u and v:
Lemma 1. For a real-valued function f defined on the vertex set of a graph G the following
conditions are equivalent:
(i) f is weakly convex;
(ii) for any two non-adjacent vertices u and v there exists w 2 I ffi (u; v) such that
(iii) any two vertices u and v at distance 2 have a common neighbour w with
Proof. (i)
Consider two vertices u and v at distance d(u; shortest paths
connecting u and v select a path
is as small as possible. Condition (iii) implies that 2f(w i
as points in the plane R Connecting the consecutive points by segments, we will get a
graph of a piecewise-linear function. This function is necessarily convex (in the usual sense),
because it coincides on P with the function f: From this we conclude that
Recall that a real-valued function f defined on a path
holds only
say that a function f defined on the vertex set of a graph
G is pseudopeakless if any two vertices of G can be joined by a shortest path along which f
is peakless [15]. Equivalently, f is pseudopeakless if for any two non-adjacent vertices u; v
there is a vertex w 2 I ffi (u; v) such that f(w) - maxff(u); f(v)g and equality holds only if
The key property of pseudopeakless functions is their unimodality, that is, every
local minimum of f is global. The proof is simple: let u be a global minimum of f and v a
local minimum of G: Consider a shortest path P between u and v along which f is peakless.
Then for any neighbour w of v we have f(w) - maxff(u); f(v)g; whence
as required. Note that every weakly convex function is pseudopeakless. The following result
constitutes a partial converse.
Remark 1. A real-valued function f defined on the vertex set of a graph G is pseudopeakless
if and only if the composition ffffif is weakly convex for some strictly isotone transformation
ff of the reals.
Proof. The property of being pseudopeakless is clearly invariant under strictly isotone transformations
of the range. Conversely, let f be a pseudopeakless function taking n distinct
values a 1 ! a ff be a strictly isotone map which assigns to each a i the
We assert that the composition ffffif is weakly convex. For given vertices u and
v at distance 2, let w be their common neighbour such that f is peakless along the path
consequently
as required. 2
In what follows we will apply Lemma 1 to the functions F - of G: The simplest instance is
given by the weight function - assigning 1 to a distinguished vertex w and 0 otherwise: then
just measures the distance in G to that vertex. We say that G is meshed [6] if
the function d(\Delta; w) is weakly convex for every choice of w: A somewhat weaker property is
used in subsequent results. Three vertices u; v; w of a G are said to form a metric triangle
uvw if the intervals I(u; v); I(v; w); and I(w; u) pairwise intersect only in the common end
vertices. If d(u; triangle is called equilateral of
size k:
Remark 2. Every metric triangle in a meshed graph G is equilateral.
To see this, suppose the contrary: let uvw be a metric triangle in G with d(u; w) ! d(v; w):
The above definition of weak convexity applied to the pair u; v; and the number
provides us with a neighbour x of v which necessarily belongs to
3. Basic characterizations. We commence by giving first answers to the questions
raised in the introduction.
Proposition 1. For a graph G the following conditions are equivalent:
(i) Med loc
weakly convex for all -;
is pseudopeakless for all -;
(iv) all level sets fx : F - (x) -g induce isometric subgraphs;
(v) all median sets Med(-) induce isometric subgraphs;
(vi) all median sets Med(-) are connected.
Any of the conditions (i) to (vi) is equivalent to the analogous condition with the additional
requirement that - be positive.
The following observation is basic for the proof of Proposition 1.
Lemma 2. If the function F - is not weakly convex on the vertex set V of a graph G for some
weight function -; then there exist a positive weight function - + and vertices u; v at distance
2 such that Med(-
Proof. If F - is not weakly convex, then by Lemma 1 there exist two vertices u and v at
distance 2 such that 2F - (w) ? F - (u) +F - (v) for all (common neighbours) w 2 I ffi (u; v): This
inequality can be maintained under sufficiently small positive perturbations of - : viz., add
any ffi satisfying
to all weights, yielding the new weights - 0
for all w 2 I ffi (u; v); that is, the initial inequality remains valid with respect to the thus
perturbed weight function. We may therefore assume that - is actually positive.
We stipulate that denote the maximum value of
Define a new positive weight function - + by
for every vertex x outside I(u; v): For w 2 I ffi (u; v) one obtains
Therefore consists only of u and v: This concludes the proof. 2
Proof of Proposition 1. The implications (ii)
are trivial, while (vi) ) (ii) is covered by Lemma 2. It remains to verify that (i) implies
(ii). Suppose by way of contradiction that some function F - is not weakly convex. By
Lemma 2 there exist a positive weight function - + and vertices u; v at distance 2 such that
Pick any ffl satisfying
and define a new weight function - 0 by
for all x Therefore both u and v are local minima of F - 0 ; but
establishes the implication (i) ) (ii).
The same arguments can be applied to prove that the analogous conditions (i + ) to (vi
additionally requiring the weight functions to be positive are all equivalent. Since (i)) (i
is trivial and (vi covered by Lemma 2, the proof is complete. 2
In view of Lemma 1(iii) and Proposition 1, all median sets are connected if and only if for
each pair u; v of vertices at distance 2 the following system of linear inequalities is unsolvable
in -:
Since LP problems can be solved in polynomial time, we thus obtain the following result.
Corollary 1. The problem to decide whether all median sets Med(-) of a graph G are
connected is solvable in polynomial time.
4. The main result. In order to obtain a convenient characterization of median con-
nectedness, we will restrict the supports of the weight functions - to be tested and then take
advantage of LP duality in the following form:
Remark 3. Let u; v be any vertices of a graph G with d(u; W be a nonempty
subset of I ffi (u; v) and X be a nonempty subset of the vertex set of G: Then for every weight
function - with support included in X there exists some w 2 W such that
if and only if there exists a weight function j with support included in W such that for every
Proof. Let D denote the submatrix of D uv (as just defined) with rows and columns corresponding
to W and X; respectively. The asserted equivalence is then a particular instance
of LP duality, as formulated by J.A.Ville (cf. [16, p.248]) in terms of systems of linear
inequalities:
For vertices x and y define the following superset of I(x;
Proposition 2. The median sets Med(-) in a graph G are connected for all weight functions
- if and only if (1) all metric triangles are equilateral and (2) for any vertices u; v with
every weight function - whose support fx included in the
set J(u; v) there exists a vertex w 2 I ffi (u; v) such that 2F - (w) - F - (u)
Proof. Necessity immediately follows from Remark 2 and Proposition 1. To prove sufficiency
assume that (1) and (2) hold but there exists a weight function - for which F - is not weakly
convex. Then by Lemma 1 there are vertices u and v at distance 2 such that
fixing u and v; we may assume that - was chosen so that this inequality still holds and
the number of vertices from the support of - outside J(u; v) is as small as possible. By (2)
we can find a vertex x with -(x) ? 0 and
To arrive at a contradiction, we will
slightly modify - by setting the weight of x to zero (and possibly transferring its old weight
to some vertex in J(u; v)): We distinguish three cases.
Case 1: jd(u; 2:
Then 2d(w; Hence the weight function - 0
defined by
contrary to the minimality assumption on -:
Case 2: jd(u;
Without loss of generality assume that d(v; be a vertex in I(u;
I(v; x) at maximal distance to x: Then x From the
latter equality and d(u; t be a vertex
in I(u; v) " I(v; x 0 ) at maximal distance to v: Since
the vertices u; t; x 0 must
constitute an equilateral metric triangle. Therefore d(u; x 2:
Define a new weight function -
For every w 2 I ffi (u; v) we have either
or
2:
Hence
and further
again a contradiction to the choice of -:
Case 3:
Let x 0 be a vertex in I(u; x) " I(v; x) at maximal distance to x: Since all metric triangles
of G are equilateral and d(u; we obtain that
2:
Define the new weight function - 0 as in Case 2. Then
and for every w 2 I ffi (u; v)
a final contradiction. 2
In view of Remark 2 we may require in Proposition 2 (as well as the Theorem below) that
G be meshed instead that all metric triangles in G be equilateral.
Let M(u; v) denote the set of those vertices of J(u; v) which are equidistant to u and v :
The neighbourhood N(x) of a vertex x consists of all vertices adjacent to x: Note that if
Lemma 3. If all median sets of a graph G are connected, then for any vertices u and v at
distance 2 there exist (not necessarily distinct) vertices s; t 2 I ffi (u; v) such that
for all vertices y 2 M(u; v):
Proof. We define a weight function - for which the hypothesis that F - be pseudopeakless
implies the asserted inequality: let
and
Since weights are zero outside M(u; v); we have F - v) such that
F - is peakless along the (shortest) path (u; s; v); that is, F -
We claim that 2: Indeed, otherwise holds and either there are two distinct
vertices there exists some vertex z 2 M(u;
I 3: In the first case we would get
and in the second case
both giving a contradiction. Now, if all vertices in M(u; v) \Gamma fsg are equidistant to s and u
(as well as v), then
and thus is the required solution to the asserted inequality. Else, there exists some
whence 2: Consequently,
and therefore s; t constitutes the required vertex pair in this case. 2
Lemma 4. Let u and v be vertices at distance 2 in a graph G; for which all median sets
are connected. Select a maximal subset S of I ffi (u; v) with the property that for each vertex
there exists a vertex t 2 S (not necessarily distinct from s) such that d(s; y)
weight function - with support included in
J(u; v) there exists some vertex w
Proof. By Lemma 3, the set S is nonempty. Now, assume the contrary and among all weight
functions violating our assertion, choose a function - for which the set
is as small as possible. This set contains some vertex x because F - is weakly convex. Pick
First suppose that d(x; distinct vertices
new weight function - 0 by
-(w) otherwise.
Then
Hence
and
for all w 2 I ffi (u; v) distinct from x; contrary to the choice of -: Therefore, x is adjacent to
all vertices possibly one vertex.
Now, suppose that d(x; for the modified weight
function - 0 defined by
-(w) otherwise
we have
Then we obtain the same inequalities as in the preceding case and thus again arrive at a
contradiction. We conclude that d(x;
If x is adjacent to all other vertices of I ffi (u; v); then 2d(x;
z 2 M(u; v); z 6= x; and hence we could adjoin x to S; contrary to the maximality of S:
Therefore, by what has been shown, I ffi (u; v) contains exactly one vertex y distinct from
x which is not adjacent to x: Since
2 there exists a vertex z 2 M(u; v) such that
necessarily
new weight function - 0 by
-(w) otherwise.
Then
giving the same contradiction as before. This concludes the proof. 2
Now we are in a position to formulate the principal result.
Theorem. For a graph G all median sets are connected if and only if the following conditions
are satisfied:
(i) all metric triangles of G are equilateral;
(ii) for any vertices u and v at distance 2 there exist a nonempty subset S of I ffi (u; v) and
a weight function j with support included in S having the two properties:
(ff) every vertex s 2 S has a companion t 2 S (not necessarily distinct from s) such
that
and
(fi) the joint weight of the neighbours of any x 2 J(u; v) \Gamma M(u; v) from S is always
at least half the total weight of S :
Proof. First assume that G is a graph with connected medians. By Proposition 2 all metric
triangles of G are equilateral. Let u; v be a pair of vertices at distance 2. The nonempty
subset S of I ffi (u; v) provided by Lemma 4 satisfies the inequality in (ff) for each s 2 S
and companion t: Moreover, Lemma 4 guarantees that for every weight function - with
support included in J(u; v) there exists a vertex w 2 S with F - (u)
duality as formulated in Remark 3 for yields a weight
function j with support included in S such that for every x 2 J(u; v) the weighted sum of
all
and therefore (fi) holds. If x 2 M(u; v); then d(s; x) - 2 for all s 2 S and
In the latter case is the companion of This yields the inequality
0; and by interchanging the role of s and t; we infer that 2:
Conversely, if conditions (i) and (ii) are satisfied, then by virtue of LP duality (Remark
conditions (1) and (2) of Proposition 2 are fulfilled, whence G has connected medians. 2
Corollary 2. All median sets in a meshed graph G are connected whenever the following
condition is satisfied:
any two vertices u and v with #I ffi (u; v) - there exist (not necessarily
vertices s; t 2 I ffi (u; v) such that
If, moreover, G satisfies the stronger condition requiring in addition that d(s; t) - 1; then
Med(-) induces a complete subgraph for every positive weight function -:
Proof. First observe that the inequality of ( ) also holds in the case that u and v are
at distance 2 with a unique common neighbour s: Indeed, if x 2 J(u; v); then necessarily
since G is meshed. To see that ( ) implies condition (ii) of the
Theorem, put trivially satisfied. For x 2 J(u;
we have d(u; x) +d(v; is meshed, and therefore x is adjacent to at least one
of s; t; thus establishing (fi):
To prove the second statement, observe that the inequality in ( ) actually holds for all
vertices x of G: Indeed, for each vertex x select a vertex x 0 from I(u; x) " I(v; x) at maximal
distance to x: Then x 0 belongs to J(u; v) and
Adding up all these inequalities each multiplied by the corresponding weight -(x) then yields
where strict inequality holds exactly when one of the former inequalities is strict for x with
positive, u and v cannot both belong to
Med(-) under these circumstances. 2
In general, we can neither dispense with weight functions nor impose any fixed upper
bound on the cardinalities of the sets S occuring in the Theorem, as the following example
shows.
Example. Let G be the chordal graph with 2
vertices comprising a set
of mutually adjacent vertices, two vertices u and v adjacent to all of
and vertices wZ associated with certain subsets Z of S; namely the sets fx 1
and fx k-subsets Y of fy such that each vertex wZ is
adjacent to u and all vertices from Z: Then a weight function j with support included in
I for the pair u; v if and only if for each of the above sets Z (which
come in complementary pairs) one has
z2Z
which is equivalent to
Thus, in order to satisfy (fi); we are forced to take a weight function j having a large support
on which it is not constant. Note that (ff) for u; v is trivially fulfilled with any choice of
from S: Finally, every other pair of vertices at distance 2 meets condition ( ) of Corollary
when either replacing u by wZ and selecting from Z or replacing u; v by wZ ; w Z 0
setting This shows that G has connected medians.
5. Particular cases. A number of graph classes [12] consist of particular meshed
graphs, for instance, the classes of chordal graphs (and more generally, bridged graphs),
Helly graphs, and weakly median graphs (see below), respectively. In the case of chordal
graphs the first statement of Corollary 2 is due to Wittenberg [26, Theorem 1.1]. Whenever
a chordal graph satisfies condition ( ), then any pair s; t selected in ( ) necessarily satisfies
comes into full action for the class of Helly graphs. A Helly graph
G (alias "absolute retract of reflexive graphs") has the characteristic "Helly property" that
for any vertices non-negative integers r the system of inequalities
admits a solution x whenever
holds [8]. Since this Helly property for (as formulated in
Lemma 1(iii)) of the function d(\Delta; z); all Helly graphs are meshed. To verify condition ( )
(with d(s; t) - 1), first observe that the Helly property for
N(v) and thus M(u; 2: Now, all vertices in
are pairwise at distance - 2; whence the Helly property guarantees
a common neighbour s: Similarly, the vertices from (N(v) " J(u; v)) [ fug have a common
neighbour t: Necessarily s; t 2 I ffi (u; v) and d(s; t) - 1 hold, and we have therefore established
the following observation, which implies the result of Lee and Chang [20] on strongly chordal
graphs (being special Helly graphs):
Corollary 3. All median sets Med(-) of a Helly graph G are connected, and moreover, if
- is positive, then Med(-) induces a complete graph in G:
In some particular classes of meshed graphs the pair s; t meeting ( ) can always be selected
by the following trivial rule: given vertices u; v at distance 2, choose any pair s; t from I ffi (u; v)
for which d(s; t) is as large as possible. Evidently, a meshed graph G satisfies condition ( )
with this selection rule provided that the following two requirements are met:
is a complete subgraph for vertices u and v at distance 2, then d(s;
induce a 4-cycle where d(s;
Notice that in (xx) we could replace the last equality by an inequality because the inequality
would imply J(s; in a meshed graph and thus the reverse inequality would follow
by symmetry. We will now show that the so-called weakly median graphs satisfy (x) and
(xx). A graph is weakly median [14] if (i) any three distinct common neighbours of any two
distinct vertices u and v always induce a connected subgraph and (ii) all functions d(\Delta; z)
satisfy the following condition, stronger than weak convexity: if u; v are at distance 2 and
Condition (ii)
is also referred to weak modularity; see [4]. Trivially, weakly modular graphs are meshed.
Remark 4. A weakly modular graph G satisfies conditions (x) and (xx) if and only if G does
not contain any of the graphs of Fig.1 as an induced subgraph. In particular, weakly median
graphs have connected medians.
@
@
@
@
@
@
@
@
@ @
\Theta
\Theta
\Theta
\Theta \Theta
@
@
@
@
@
@
@
@
@ @
\Theta
\Theta
\Theta
\Theta \Theta
@
@
@
@
@
@
@ @
s
x
s
x
s
(a) (b) (c)
Fig. 1
Proof. If G includes an induced subgraph from Fig. 1, then s; t; u; v; x violate either (xx)
or (x). Conversely, assume that G is weakly modular but violates (x) or (xx) for some
vertices s; t; u; v; x: Then, as x 2 J(u; v); we have d(u; x)+d(v; x) - 3 by weak modularity. If
necessarily s; t; u; v; x induce one of the first two graphs in Fig. 1. Otherwise,
say, As G is meshed, u; v; x have some common
neighbour w: If w is not adjacent to both s and t; then we are back in the preceding case
with w playing the role of x: Therefore we may assume that w is a common neighbour of s
and t: If s and t are not adjacent, then s; t; u; v; w induce a subgraph isomorphic to Fig. 1b.
Otherwise, s and t are adjacent, and we obtain the graph of Fig. 1c as an induced subgraph.
Finally, note that the latter graph minus v as well as Fig. 1a,b are all forbidden in a weakly
median graph. 2
Inasmuch as pseudo-median graphs and quasi-median graphs are weakly median, Remark
4 (in conjunction with Proposition 1) generalizes some results from [3, 7, 17, 24]. Another
class of meshed graphs fulfilling (x) and (xx) is associated with matroids. A matroid M can be
defined as a finite set E together with a collection B of subsets (referred to as the bases of M)
such that for there exists some e
The basis graph of M is the (necessarily connected) graph whose vertices are the bases of M
and edges are the pairs B; B 0 of bases differing by a single exchange. We immediately infer
from the characterization established by Maurer [21] that the basis graph of every matroid
is meshed (but not weakly modular in general) and satisfies (x) and (xx).
Corollary 4. The basis graph of every matroid has connected medians.
In view of Corollary 4 and Proposition 1 one can solve the median problem in the basis
graph of a matroid with the greedy algorithm. Given a weight function - on
assign a weight to each element e 2 E by
Applying the greedy
algorithm one finds a base B   maximizing the function B 7!
We assert that B   is a minimum for the function F - in the basis graph. Indeed, if
is any neighbour of B   ; then
Hence B   2 Med loc
(-) =Med(-); as required.



--R

On conditions of coincidence of local and global extrema in optimization problems (in Russian)


A Helly theorem in weakly modular space
decomposition via amalgamation and Cartesian multiplication
Weak Cartesian factorization with icosahedra
Graph Theory
Dismantling absolute retracts of reflexive graphs




The Geometry of Geodesics
Separation of two convex sets in convexity structures
Discrete Math.

Medians of pseudo-median graphs (in Russian)
On graphs with prescribed median I
On conditions of coincidence of local and global minima in problems of discrete optimization

Matroid basis graphs I
The median procedure in a formal theory of consensus
Medians of arbitrary graphs
The solution of the Weber problem for discrete median metric spaces (in Russian)
a survey I
Local medians in chordal graphs
--TR

--CTR
Victor Chepoi , Clmentine Fanciullini , Yann Vaxs, Median problem in some plane triangulations and quadrangulations, Computational Geometry: Theory and Applications, v.27 n.3, p.193-210, March 2004
majority rule;local medians;LP duality;medians;graphs