NIST Special Publication 500-303 

The Structure of Optimal and Near 

Optimal Target Sets in Consensus 

Models 

Fern Y. Hunt 

This publication is available free of charge from: 

http://dx.doi.org/10.6028/NIST.SP.500-303 
 

NIST Special Publication 500-303 

The Structure of Optimal and Near 

Optimal Target Sets in Consensus 

Models 

Fern Y. Hunt 

Applied and Computational Mathematics Division 

Information Technology Laboratory 

This publication is available free of charge from: 

http://dx.doi.org/10.6028/NIST.SP.500-303 

August 2014 

U.S. Department of Commerce 

Penny Pritzker, Secretary 

National Institute of Standards and Technology 

Willie May, Acting Under Secretary of Commerce for Standards and Technology and Acting Director 
Certain commercial entities, equipment, or materials may be identified in this 

 document in order to describe an experimental procedure or concept adequately. 

Such identification is not intended to imply recommendation or endorsement by the 

National Institute of Standards and Technology, nor is it intended to imply that the 

entities, materials, or equipment are necessarily the best available for the purpose. 

National Institute of Standards and Technology Special Publication 500-303 

Natl. Inst. Stand. Technol. Spec. Publ. 500-303, 20 pages (August 2014) 

CODEN: NSPUE2
 

This publication is available free of charge from: 

http://dx.doi.org/10.6028/NIST.SP.500-303 
�

1 

The Structure of Optimal and Near Optimal Target Sets in

Consensus Models

Fern Y. Hunt

Applied and Computational Mathematics Division

National Institute of Standards and Technology

Gaithersburg,Maryland 20899

August 18, 2014

Abstract 

We consider the problem of identifying a subset of nodes in a network that will enable 

the fastest spread of information in a decentralized environment.In a model of communication 

based on a random walk on an undirected graph, the optimal set over all sets of the same 

or smaller cardinality minimizes the sum of the mean first arrival times to the set by walkers 

starting at nodes outside the set. The problem originates from the study of the spread of 

information or consensus in a network and was introduced in this form by V.Borkar et al. in 

2010. More generally, the work of A. Clark et al. in 2012 showed that estimating the fastest 

rate of convergence to consensus of so-called leader follower systems leads to a consideration of 

the same optimization problem. 

The set function F to be minimized is supermodular and therefore the greedy algorithm is 

commonly used to construct optimal sets or their approximations. In this paper, the problem is 

reformulated so that the search for solutions is restricted to optimal and near optimal subsets of 

the graph. We prove sufficient conditions for the existence of a greedoid structure that contains 

feasible optimal and near optimal sets. It is therefore possible we conjecture, to search for 

optimal or near optimal sets by local moves in a stepwise manner to obtain near optimal sets 

that are better approximations than the factor (1 − 1/e) degree of optimality guaranteed by the 

use of the greedy algorithm. A simple example illustrates aspects of the method. 

Random Walk Consensus Model 

Given a connected graph G = (V, E), with vertices or nodes V and edges E, we imagine a random 

walker situated at a node i ∈ V , moving to another node j ∈ V in a single discrete time step. The 

choice of j is random and has probability, 

pij > 0, if (i, j) ∈ E P rob{i → j} = (1) 

pij = 0 otherwise. 

The matrix P = (pij )i,j=1···N is the transition matrix of a Markov chain which in this paper, is 

assumed to be irreducible and aperiodic ([7]). N is the number of nodes and as in [1] the spread 

of information is described in terms of a process that is dual to the movement from informed to 

uninformed nodes. A random walk begins outside a pre-determined set A of informed target nodes 

1 
and ends at A. Starting at node i /∈ A, a random walker first reaches the set A at a hitting time 

TA = min{n > 0 : Xn ∈ A}, where Xn is the node occupied by the walker at time n. The hitting 

time is closely related to the rate of convergence in a leader-follower model of Clark et al., as well 

as other consensus models [3, 10], [1]. The effectiveness of a set A in the spread of information by 

random walks can then be measured by, 

 

F(A) = h(i, A) , (2) i /∈A 

where h(i, A) = Ei[TA], is the expected number of steps to A starting at node i. When F(A) is 

small, A is a desirable choice of informed nodes, but is a poor choice if F(A) is large. A standard 

result in Markov chain theory tells us that h(i, A) is the ith component of the vector H, which solves 

the linear equation. 

H = 1 + PAH (3) 

where 1 is a column vector of N − |A| ones and PA is the matrix that results from crossing out 

the rows and columns of P corresponding to the nodes of A [7]. Limited resources can constrain 

the maximum size of the subset to be selected so it makes sense then to ask for the most effective 

spreader subject to a cardinality constraint, i.e. 

min F(A) (4) A⊂V, |A|≤M 

Borkar et al. [1] showed that for arbitrary subsets A, B ⊆ V , F(A∩B)+F(A∪B) ≥ F(A)+F(B), 

that is, F is a supermodular function. Clark et al. in [3] discussed a continuous time leader-follower 

problem where a set A of leader nodes are assigned fixed function values and the remaining follower 

nodes update their function values by weighted exchange with their neighbors with weights defined 

by equation (1). If G is strongly connected, the node function values converge to a consensus value 

(vector) determined by the leader nodes and the rate of convergence has a connection to precisely 

the random walk problem we are describing. In [3], two optimization problems are posed. The first, 

is to select up to M leaders in order to minimize the convergence error. Given the random walk 

connection the problem in Clark is equivalent to the the problem posed in equation (4). 

Since F is supermodular, both references [1],[3] make use of the work of [11] to devise a greedy 

algorithm that builds an approximate solution to the optimization problem (4) in a stepwise fashion 

until a set of cardinality M is reached. Recall that at the first stage of construction, the node with 

the smallest value of F among the nodes is selected. At the pth stage the node is added to the set 

that results in a set of cardinality p+1 with the smallest value of F. Using the results of [11], Borkar 

et al. were able to give some guarantee of the quality of the approximation of a weaker version of ∗ the optimization problem with the additional constraint that the set contain an element {a}. If Fa 

is the optimal value of this weaker optimization problem and AM (a) is the greedy approximation 

obtained by starting the algorithm with the set {a}, then 

1 ∗ F({a}) − F(AM(a)) ≥ (1 − )(F({a}) − F ) (5) a e 

In the continuous time setting, Clark et al. obtained a similar inequality but it is independent of 

the choice of a required initial element. 

It will be instructive in what follows to see the results of applying the greedy algorithm to a 

specific graph. In all the examples discussed in this paper we assume that for every neighbor j of 

1 node i, p(i, j) = deg(i) . 

2 
EXAMPLE 1 Figures 1-5 show the picture of a graph G with 9 nodes including the nodes of 

the optimal set of cardinality K for K = 1 through 5. In this example the optimal set of a given 

cardinality does not contain an optimal subset that is one element smaller. Thus, for example the 

optimal 3 element set cannot be obtained from the (unique) 2 element set. In turn the 2 element 

set does not contain the 1 element optimal set. Therefore the greedy algorithm does not produce 

optimal sets. 

In this paper,the optimization problem is reformulated with a view towards improving the guarantees of the greedy algorithm proved in [1], [3]. We seek solutions or approximations of the problem 

for some cardinality M where M < K where K fixed, is the cardinality of a vertex cover of the 

graph. A vertex cover is an optimal set for its cardinality, so we first seek solutions of problem (4) 

that are subsets of the cover. This is done in section 2 in order to provide motivation for our method. 

Since (as we show) it is not always possible to find optimal subsets in an arbitrary vertex cover, the 

search space is enlarged to a class of optimal and near optimal sets of a specified degree of optimality 

relative to the vertex cover (see the definition in (9)). These sets are introduced in section 2.2. Our 

main result is a sufficient condition for the existence of a gredoid structure containing optimal and 

near optimal sets (see Theorem 1 and Corollaries 1 and 2). The properties of the greedoid enable 

one to make local moves (for example by adding or deleting certain elements of a set) that preserve 

the optimality or near optimality of feasible sets. We have observed that solutions of the original 

optimization problem are well approximated by high ranking near optimal sets and the quality of the 

approximations can exceed the (1−1/e) factor guaranteed by the greedy algorithm. In section 2.3 we 

show an illustrative example. The key is the ability to improve the approximations by searching the 

greedoid structure. This is formalized in section 3.1, where we briefly introduce the greedoid graph 

whose nodes are feasible sets. Properties of adjacent nodes in this graph enable local moves among 

sets that can be used to improve approximations and thus lay the groundwork for deterministic local 

search methods such as branch and bound on the one hand or stochastic search on the other. The 

paper concludes in section 4 with a summary of the results and questions for further research. 

2 Finding and Approximating Optimal Sets 

2.1 Maximal Matches 

The optimization problem as posed in equation(4) assumes no advance knowledge about the optimal 

set or other possibly related subsets of G. In this section we seek to explore alternative formulations 

of the problem that could lead to better approximations of the optimal set. The next definition will 

be helpful in the discussion that follows: 

Definition 1 A vertex cover of a graph G = (V, E) is a set of vertices that are incident to every 

edge in E. 

Lemma 1 Let A be a vertex cover of the graph G, with K = |A|. Then A solves the optimization 

problem (4) for M = K. 

Proof: Since every edge of G is incident to an element of A, a random walker starting at a vertex 

i outside of A must hit A at the first step. That is h(i, A) = 1. Now equation (3) implies that 

h(i, A) ≥ 1 so it follows that A must be an optimal set for its own cardinality. � 

3 
Thus the problem of finding an optimal subset is partially resolved if one can construct a vertex 

cover. Fortunately, there is a simple greedy algorithm (sometimes called the Two Opt algorithm) 

for constructing a maximal match, whose vertices are a vertex cover. 

Definition 2 A maximal match of a graph is a set of edges that are non-adjacent (i.e. they do 

not share a common vertex). The set is maximal in the sense that there is no larger set with this 

property. 

As is well known [6], the vertices of a maximal match form a vertex cover. To see why note that every 

edge e in E is either an edge of a maximal match or is adjacent to such an edge. Thus e contains a 

vertex in the match. That is, e is incident to some vertex in the match so the definition of vertex 

cover is satsified. Now let M be the set of vertices of the maximal match that was constructed using 

the Two Opt algorithm. It can be shown ([4]) that, 

OP T ≤ |M| ≤ 2 · OP T, (6) 

where OP T is the cardinality of the minimal vertex cover. The run time of Two Opt is O(|E|) 

[4]. Because supersets of a vertex cover are optimal sets and since we observe that optimal sets are 

often subsets of a vertex cover, it is natural to seek solutions of the optimization problem among 

the subsets of M: 

min F(A). (7) A⊂M,|A|≤M 

Recall that the graph in EXAMPLE 1 has optimal sets which cannot be found by application of 

the greedy algorithm. However when the Two Opt algorithm is used to obtain edges of a maximal 

match (1, 3),(5, 6),(7, 8), the vertices M, contain optimal subsets for M = 1, 2, 3, 4, 6. In contrast 

to the greedy approach of building up to an optimal set, we start with a maximal match and obtain 

optimal sets of smaller cardinality as subsets. Unfortunately as the next example illustrates, this 

approach is not always successful. 

EXAMPLE 2: 

The vertices of two maximal matches for a graph are shown in Figure 6. The figure on the left shows 

a maximal match whose vertex set M contains no optimal subsets except itself while the match 

shown on the right contains subsets that are optimal sets for M = 1 through 4. Both maximal 

matches were obtained using the Two Opt algorithm. 

Do we have a way to predict when optimal sets of predetermined cardinality are contained in 

a maximal match? Presently we do not. The reason is that optimality is not always preserved by 

adding or removing elements from a single optimal set. However as discussed in the next section 

and 3.1 there is a greedoid containing optimal and near optimal sets (see the definition in 9) with 

a structure that is preserved under such operations. Moreover in section 3 we prove sufficient 

conditions for a vertex cover to contain optimal and near optimal subsets (Proposition 4). 

2.2 Optimal and Near Optimal Sets 

In section 1 a measure of the spread effectiveness of sets was introduced in (2). It will be convenient 

to convert this to a rank defined on subsets of V . In particular, suppose there exists a maximal 

match with K vertices. We will order all non-empty subsets A ⊆ V such that |A| ≤ K with a 

ranking function ρ(A) defined as, 

Fmax − F(A) ρ(A) = (8) Fmax − Fmin 

4 
where Fmax = max∅ =A⊆V |A|≤K F(A), and Fmin is the corresponding minimum. Fmin can be calculated by computing F for a maximal match of cardinality K, while Fmax is the maximal value of 

F among all one element subsets. We assume that Fmax = Fmin. If this were not the case, F(A)

would have the same value for any non-empty subset A with |A| ≤ K. Thus any A would be a 

solution of the problem. 

If A is optimal set of cardinality K, then ρ(A) = 1, the maximum value of ρ, conversely the 

worst performing set has value 0. An optimal set of size M < K, has the largest ρ value among sets 

of size M. For a constant c, 0 < c ≤ 1 and K, the non-empty set 

Lc,K = {A : A ⊆ V, |A| ≤ K, ρ(A) ≥ c} (9) 

defines a set of optimal and near optimal subsets, with the degree of near optimality depending of 

course on c. The structure of optimal and near optimal sets is conveniently described in terms of a 

concept in combinatorial optimization known as a greedoid [9, 2]. 

Definition 3 Let E be a set and let F be a collection of subsets of E. The pair (E, F) is called a 

greedoid if F satisfies 

• G1 : ∅ ∈ F 

• G2 : For A ∈ F non-empty, there exists an a ∈ A such that A \ {a} ∈ F 

• G3 : Given X, Y ∈ F with |X| > |Y |, there exists an x ∈ X \ Y , such that Y ∪ {x} ∈ F 

A set in F is called feasible. Note that G2 implies that a single element can be removed from 

a feasible set X so that the reduced set is still feasible. By repeating this process the empty set 

eventually is reached. Conversely starting from the empty set, X can be built up in steps using the 

G3 property. 

Our first step is to show that Lc,K satisfies condition G3 of the definition for 0 < c ≤ 1, 0 ≤ K ≤ N 

(Proposition 1). The proof depends on several short lemmas. The first uses an adaptation of an 

argument in Clark et al. 

Lemma 2 Let S ⊆ V , u ∈ V \ S. Then F(S) ≥ F(S ∪ {u}). 

Proof: Suppose S, a set of nodes is a target set for the random walk. Let El (S) be the event, ij

El (S) = {X0 = i ∈ V, Xl = j ∈ V \ S, Xr ∈/ S, 0 ≤ r ≤ l}. Thus paths of the random ij

walk start at i and arrive at j without visiting S during the interval [0, l]. Also define the event 

Fl (S, u) = El (S) ∩ l {X(m) = u} where u /∈ S. Paths in this event also start at i and arrive ij ij m=0 

at j without visiting S, but must visit the element u at some time during the interval [0, l]. Since a 

path either visits u in the time interval [0, l] or it does not, it follows that: 

El 

ij(S) = El ij(S ∪ {u}) ∪ Fl ij(S, u) (10) 

We have El 

ij(S ∪ {u})

n Fl 

ij(S, u) = ∅. This implies that, 

χ(El 

ij(S)) = χ(El ij(S ∪ {u})) + χ(Fl ij(S, u)) (11) 

and therefore: 

χ(El ≥ χ(El 

ij(S)) ij(S ∪ {u}) (12) 

5 
Here χ(A) is the indicator function of the set A. Recalling that TS is the hitting time for set S,

the following relation comes from taking the expection of χ(El

ij(S)) on the left hand side of (12)

summing over all j ∈ V \ S. Here E denotes expectation.

Prob{TS > l|X0 = i} = E





X

j∈V \S

χ(E

l

ij(S))



 (13)

A similar result is obtained for TS∪{u} from taking the expectation of χ(El

ij(S ∪ {u})) on the right

hand side of (12) and summing over j ∈ V \ S. Summing once again over all l ≥ 1 results in the

inequality,

h(i, S) ≥ h(i, S ∪ {u}) (14)

Finally on summing (14) over all i and recalling the definition of F (equation (2)) one obtains the

result to be proved. ✷

The following result uses that fact that F is supermodular.

Lemma 3 For c > ̄ 0, let P = {X ⊆ V : F(X) ≥ c > ̄ 0}. If A, B ∈ P where |A| = |B| and

|A ∩ B| = |A| − 1, then A ∩ B ∈ P.

Proof: The hypothesis implies the existence of a set X such that A = X ∪ {a} and B = X ∪ {b}

with a 6= b, a, b, ∈ V . The supermodular property of F implies that:

F(X ∪ {a} ∪ {b}) + F(X) ≥ F(X ∪ {a}) + F(X ∪ {b}) (15)

Rearranging we have,

F(X) ≥ F(X ∪ {a}) + [F(X ∪ {b}) − F(X ∪ {a} ∪ {b})] (16)

Thus on writing X = A∩B, using the hypothesis on A, and then applying Lemma 2 to the bracketed

quantity, we have,

F(A ∩ B) ≥ F(A) ≥ c ̄

✷.

The following lemma is part of a result in [9, 2] on paving greedoids.

Lemma 4 If P is any class of sets satisfying the conclusion of Lemma 3, S = 2V \P has property

G3. That is, given any A, B ∈ S , with |A| > |B|, there is an a ∈ A \ B such that B ∪ {a} ∈ S .

Proof: Suppose the conclusion is false. If |A \ B| = 1, then for a ∈ A \ B, B ∪ {a} ∈ P. But

A = B ∪ {a}. To see this suppose there is some a

0

6= a that is not in B. Then A \ B contains

a

0

so |A \ B| > 1 so this is a contradiction. Thus A = B ∪ {a}, but A ∈ S , and this is also a

contradiction. Suppose next that |A \ B| > 1. Then there exists a, a

0

∈ A \ B. We have B ∪ {a}

and B∪{a

0

} ∈ P. Thus the conclusion of Lemma 3 implies that B ∈ P, which is a contradiction. ✷

Proposition 1 For 0 < c ≤ 1 and 0 < K ≤ N, let Lc,K be the class of sets defined in equation (9).

Then Lc,K satisfies condition G3.

6
G

Proof: If P is the set defined in Lemma 4 then Lc,K = S for some c. In fact we may set 

Fmax −c ̄ c = . If Fmin ≤ c ̄ ≤ Fmax , we have 0 ≤ c ≤ 1. Lc,K satisfies the conclusion of Lemma 4 Fmax −Fmin 

and therefore it satisfies property G3. � 

The proposition establishes that Lc,K satisfies the G3 property for greedoids. However, G2 does 

not hold. For example if the set A has cardinality m where m is the size of the smallest set in Lc,K 

then A \ {a} cannot be in Lc,K for any element a ∈ A. Conversely, let cm = max|X|≤m ρ(X). If 

cm ≥ c > cm−1 then m is the size of the smallest set in Lc,K . To create a class of sets with the 

G2 property, one constructs subsets of Gm of size n ≤ m that satisfy G3, while sets Gn for n > m 

are culled so the remaining sets satisfy G2. The greedoid will then consist of selected subsets and 

supersets of Gm This construction is illustrated in the next section (section 2.3) where an example 

of a greedoid is presented and our proposed method for solving problem (4) is demonstrated. It is 

based on restricting the search for solutions to feasible optimal and near optimal sets in the greedoid. 

Following this, in section 3, sufficient conditions for the existence of a greedoid are presented as well 

as proofs. 

2.3 Greedoid Based Approach to the Optimization Problem 

Let G be the graph discussed in EXAMPLE 1 of section 2.1. The smallest sets in L7/8,8 have 

cardinality m = 2. Any sets in L7/8,8 will have guaranteed degree of optimality 7/8 as defined by 

equation (8). Our method is based on searching for optimal and near optimal sets that are the 

feasible sets of the greedoid constructed from G2. Values of F for two element sets are computed 

in advance to start the procedure. In addition to G2 itself, the empty set and selected one element 

subsets of G2 must also be included. These sets arise from the pairwise intersection of sets in G2 

(listed below) and in addition they must satisfy G3 for every set in G2. The two element sets are: 

Elements of G2 = G2 

{3, 7} ∗ , {2, 8} (17)

{1, 7} ∗ , {1, 9}

{2, 7}, {2, 9}

{3, 8} ∗ , {5, 7} ∗

{3, 9}, {1, 4}

{3, 4}, {1, 6} ∗

{3, 6} ∗ , {2, 4}

{1, 8} ∗ , {2, 6}

The one element sets of the greedoid are therefore GG1 = {1, 2, 3, 7}. The two element feasible sets 

are defined to be supersets of GG1. Here that is all of G2, no culling is necessary. Once n > m, 

the feasible sets of the greedoid are subsets of Gn that are supersets of GGn−1. Thus feasible sets 

of cardinality 3, GG3 are sets in G3 that are supersets of GG2. It will be helpful in our discussion of 

the method to list some of the elements in the greedoid. It can be checked that the displayed sets 

7 
satisfy G1-G3. 

10 elements of GG3 10 elements of GG4 10 elements of GG5 (18) 

{3, 4, 9} {2, 5, 7, 9} {2, 3, 4, 6, 9} 

{3, 6, 8} {2, 5, 7, 8} {2, 3, 4, 6, 8} 

{1, 5, 7} {1, 5, 7, 9} {1, 3, 4, 6, 9} 

{2, 5, 7} {1, 5, 7, 8} {1, 3, 4, 6, 8} 

{3, 4, 7} {3, 4, 6, 9} {2, 3, 6, 7, 8} 

{3, 5, 7} {3, 4, 6, 8} {2, 3, 5, 7, 9} 

{3, 7, 9} {3, 6, 7, 8} {2, 3, 5, 7, 8} 

{3, 6, 7} {3, 5, 7, 9} {2, 3, 4, 7, 9} 

{3, 7, 8} {3, 5, 7, 8} {2, 3, 4, 6, 7} 

{3, 4, 6} {3, 4, 7, 9} {1, 3, 6, 7, 8} 

Suppose we try to solve the optimization problem (4) for M = 5. One could exhaustively compare 

the F values for all possible 5 element subsets. Alternatively, one could apply the greedy algorithm 

to the best single node(s).The thesis of this paper is that one can reduce the number of 5 element 

sets to the smaller class of near optimal sets. For any c > 0 this class contains optimal 5 element sets 

and approximations that are better than the guarantees of the greedy algorithm approximations. 

The greedoid properties enable the near optimal sets to be constructed from one-element sets in 

a stepwise manner. Given the vertex cover for our example graph G, V C = {1, 3, 5, 6, 7, 8} , a 

selection of two element sets in G

G2 that are also subsets of V C (indicated in display (17) by stars) 

was used to create a sample of 5 element candidate sets to be compared. Each starred 2 element set 

was greedily extended to a 5 element candidate set, step by step. The left most column of display 

(19) shows the 3 element sets obtained from a greedy one element extension of the 2 element sets. 

The next column shows the corresponding F values of each set. The third column is a list of the 

4 element sets obtained by a one element greedy extension of the 3 element sets. The column of 

corresonding F values appears next. Finally the fifth and sixth columns contain the 5 element sets 

and the corresponding F values respectively. 

Our method is to offer the 5 element set with smallest F value as the approximate(or actual) 

solution of the problem.In this case the set we obtain, A = {2, 3, 4, 6, 8} is a solution. Note that the 

same procedure can be used to obtain the solutions to the problem for M = 3 ({3, 6, 8}) and M = 4 

({2, 5, 7, 8} or {1, 5, 7, 9}). The set {1, 5, 7, 8} is symmetric to the latter sets so it is left out. 

This example illustrates two more additional advantages of the greedoid structure of optimal 

and near optimal sets. Optimal solutions that are not subsets of the vertex cover but that are in 

the greedoid can still be found by these methods. For example, A is not a subset of V C. Secondly, 

an approximate solution can be improved using greedoid properties G2 and G3. Thus given an 

approximation B = {2, 3, 4, 6, 7} with F(B) = 5.00, the sequence {2, 3, 4, 6, 7} → {3, 4, 6, 7} → 

{3, 4, 6} → {3, 4, 6, 8} → A = {2, 3, 4, 6, 8}.Thus swapping the elements 7 in B with 8 in A preserves 

near optimality and in fact improves the value of F. Thus we conjecture that navigation through 

the greedoid offers a systematic way of accessing highly optimal solutions. Section 3.1 elaborates on 

8 
3 

this idea. 

{3, 4, 7} 12.4 {3, 4, 7, 9} 8.00 {1, 3, 4, 7, 9} 5.00 (19) 

{3, 6, 7} 12.4 {3, 4, 6, 7} 8.00 {2, 3, 4, 6, 7} 5.00 

{1, 5, 7} 11.8 {1, 5, 7, 9} 7.40 {1, 2, 5, 7, 9} 5.00 

{2, 5, 7} 11.8 {2, 5, 7, 8} 7.40 {1, 2, 5, 7, 8} 5.00 

{3, 6, 8} 11.6 {3, 4, 6, 8} 7.82 {2, 3, 4, 6, 8} 4.82 

{1, 4, 6} 13.9 {1, 4, 6, 9} 9.04 {1, 4, 5, 6, 9} 6.21 

The Structure of Optimal and Near Optimal Target Sets 

In this section we discuss how given a fixed c, a measure of near optimality and K the size of the 

largest optimal set under consideration, a greedoid can be constructed from the set Lc,K of optimal 

and near optimal sets. Two sufficient conditions are presented (see Case I and Case II) for the 

construction of a greedoid. Corollaries 1 and 2 describe the feasible sets of the greedoid for Cases I 

and II respectively. 

In order to construct a greedoid of optimal and near optimal sets one must construct a class 

of sets from Lc,K that satisfy G2 as well as G3. The process can proceed along two tracks- one 

for sets of cardinality n ≤ m and the second for sets of cardinality n ≥ m. For the latter, let 

Gn = {A ∈ Lc,K, |A| = n} for n ≥ m. Lemma 4 shows that Lc,K satisfies G3. We set Gm = gm. 

Suppose GGn, for m ≤ n ≤ K,( respectively {Ggn}1≤n≤m ) is a class of supersets (respectively subsets) 

of GGm of cardinality n, with the properties: 

T1 Ggm = GGm ⊆ Gm 

T2 Every A ∈ Ggn, contains a subset B ∈ Ggn−1. 

T3 For every B ∈ gGn−1, and A ∈ gGn, there is p ∈ A \ B such that B ∪ {p} ∈ gGn. 

T4 For n > m, GGn = {A|A ∈ Gn A ⊃ B, B ∈ GGn−1}, 

then the collection of sets Fc,K = { ∅, (gGn, 1 ≤ n ≤ m), (GGn, m ≤ n ≤ K), } are the feasible sets 

for a greedoid over ground set V . This follows from Lemma 5 and its consequence Theorem 1. 

Lemma 5 : Suppose GGn, n ≥ m,(respectively Ggn n < m ) are supersets (respectively subsets) of Gm 

that satisfy T1-T4. Then: 

(1) fm = { ∅, (Ggn, 1 ≤ n ≤ m) } satisfies G1 and G2. 

(2) If A ∈ GGn for n > m, there is an a ∈ A such that A \ {a} is in GGn−1. 

(3) If B ∈ gGn, n < m and A ∈ fm or ∈ Gk, k ≥ m, with |A| > |B|, then there is an a ∈ A such that 

B ∪ {a} ∈ Ggn+1. 

Proof: For statement (1) G1 is clear. By T2 for any A ∈ Ggn there is a subset B ∈ Ggn−1. Since 

A has cardinality n and B has cardinality n − 1 we must have B = A \ {a} for some a. Thus G2 

holds. The proof of statement(2) is the same as the proof of the G2 property for fm where here T4 

is used. To show (3), first suppose A ∈ Ggk, k > n. By (1) we may apply G2 repeatedly to reduce 

9 
� � �

A to a set A g ∈ Gn+1. Then by T3, B ∪ {a} ∈ gGn+1 for some a ∈ A \ B. Since A ⊆ A, we have

a ∈ A. Next if A ∈ GGk for k ≥ m, either A ∈ GGm or (2) can be applied repeatedly to produce a set 

in Gˆm. By T1, GGm = Ggm so A is reduced finally to a set in fm. Thus we obtain the conclusion by

repeating the argument used in the previous case. �. 

Theorem 1 The class of sets Fc,K = { ∅, (gGn, 1 ≤ n ≤ m − 1), (GGn, m ≤ n ≤ K)} is a class of 

feasible sets for a greedoid over V . 

Proof: By Proposition 1, G3 is satisfied when A ∈ G

Gn since G

Gn ⊆ Gn. G3 is established for 

A ∈ gGk by Lemma 5 (3). Property G2 for A ∈ GGn follows from Lemma 5 (2) when n > m and 

Lemma 5 (1) and T1 when A ∈ GGm = gGm. If A ∈ gGk, then A satisfies G2 because of Lemma 5 (1).

Finally Fc,K clearly contains ∅. �. 

Theorem 1 describes the feasible sets of the greedoid formed by sets Ggn and GGn when T1 − T4 

are satisfied. We next present two sufficient conditions for the existence of sets satisfying T1-T4. 

Case I: Suppose Gm is a single set Gm = GGm = {H}. For n = m − 1, define ˆgm−1 to be the 

class of subsets of H of cardinality m − 1. When n < m − 1, Ggn−1 = {B|B ⊂ H, |B| = n − 1}. GGn 

is a superset of Gm obtained by stepwise addition of elements as described in T4. If Gm has more 

than one set an arbitrary H can be selected. 

Corollary 1 The collection of sets {Ggn|n ≤ m} and {GGn|n > m} in Case I, satisfy conditions 

T1 − T4, therefore F(Lc,K) = {∅, (B : B ⊂ H, |B| < m), H, (A|A ⊃ H, |A| ≤ K)} are the feasible 

sets of a greedoid. 

Proof: T1 and T2 follow directly from the definitions of GGn and gGn. The property T3 holds. To 

see this suppose A ∈ gGn and B ∈ Ggn−1. Since A and B are subsets of H, A has at least one element 

p that is not in B. Now ˆgn contains all subsets of H of cardinality n it must have B ∪ {p}. T4 

follows immediately from the definition of GGn. �. 

To describe the second sufficient condition for the existence and construction of a greedoid we 

will need a couple of definitions. 

Definition: Given subsets A and B of V , with an element p ∈ V \ B such that A = B ∪ {p}, 

A is a parent of B and p is a partner of B. 

As before members of Gn are elements of Lc,K of cardinality n ≥ m and gn are subsets of Gm of 

cardinality n ≤ m. However in the present situation, sets in gn will be defined in terms of pairwise 

intersections of sets of cardinality n + 1. Specifically let Un = {B : B = C ∩ A, |A| = |C| = n + 1}. 

Then for n < m we define by backward induction starting from m, 

gn = {B ∈ Un|B = E ∩ F, E, F ∈ gn+1}. 

Thus elements in gn subsets of size n are pairwise intersections of adjacent pairs (in the Hamming 

metric sense) of sets in gn+1. 

The second sufficient condition is defined in terms of the following sets: let Xp,k = {A|A ∈ 

gk, A = S ∪ {p}, |S| = k − 1} , Yp,k = {W|W ∈ gk−1, W ∪ {p} ∈ gk}. The set A is in Xp,k if it 

10 
 

 

contains p and is the parent of an S with cardinality k − 1. A set W is in Yp,k if it has a partner p. 

Proposition 2 Suppose B ∈ gn where n < m. Further suppose there is a finite set {pi ∈ V : i = ln 1 · · · ln} (which may depend on B), such that gn+1 = Xpi,n+1 where pi ∈/ B, i = 1 · · · , ln, and i=1 

B ⊂ nln Yp,,n+1 = ∅. Then for every A ∈ gn+1, there exists a p ∈ A \ B such that B ∪ {p} ∈ gn+1. i=1 

Proof: The hypothesis states that B has partners, pi ∈/ B, i = 1, · · · ln. Moreover we also have 

that each A ∈ gn+1 contains an element, say p in this set by hypothesis. Thus by the definition of 

partner, we must have B ∪ {p} ∈ gn+1. � 

The shorthand notation B � gn+1 used in the sequel means that B satisfies the hypothesis of 

Proposition 2. Therefore as a consequence of the conclusion, B satisfies T3. 

Case II 

• (i) For every 1 ≤ n ≤ m, Ggn = {B ∈ gn | B � gn+1, B ⊃ C, C ∈ gGn} = ∅. 

• (ii) Ggm = GGm = {A ∈ Gm|A ⊃ B, B ∈ gGm−1}. 

• (iii) GGn = {A ∈ Gn|A ⊃ B ∈ Gn−1} , n > m. 

REMARK: If property (i) is true then for every n < m, there are elements in gn that satisfy the 

hypotheses of Proposition 2. 

Case II is illustrated in the example discussed in section 2.3. Here the one element feasible sets are 

are gG1 = {{1}, {2}, {3}, {7}}. The elements {4},{5},{6},{8},{9} are excluded even though these sets 

arise from the pairwise intersection of sets in G2, because they fail to satisfy (i) and therefore they 

do not satisfy T3 (and thus G3). 

Proposition 3 If CASE II holds, then T1-T4 is satisfied. 

Proof: T1 and T2 follow easily from (i) and (ii). To see that T3 holds note that it is a consequence 

of (i) since B � Ggn+1 and any A ∈ gGn is in gn. T4 follows from (iii). �. 

Corollary 2 Suppose {Ggn} 1 ≤ n ≤ m and {GGn} m ≤ n ≤ K satisfy the conditions of Case II.Then 

the class of sets F(Lc,K) = {∅, (gGn, 1 ≤ n ≤ m − 1), (GGn, m ≤ n ≤ K)} are the feasible sets of a 

greedoid. 

Proof: By Proposition 3, the hypotheses of Theorem 1 are satisfied. Thus the conclusion of this 

proposition follows from the theorem. �. 

When M is a vertex cover (e.g. the vertices of a maximal match) then we can give a partial 

answer to the question raised in section 2 of when vertex covers contain optimal sets. If M is a 

feasible set with |M| > m, then it will contain optimal or near optimal sets where the degree of 

optimality is defined by c in (9). 

11 
Proposition 4 : Let M be the vertices of a vertex cover (maximal match) and suppose c and K 

as in (9) are given. Further let m be the minimum cardinality of sets in Lc,K. If |M| > m, and M 

is a feasible set of the greedoid in Theorem 1, then it and its subsets with cardinality at least m are 

in Lc,K.Thus it has nearly optimal subsets. In particular if there is an S ∈ GGm with S ⊂ M, then 

M has nearly optimal subsets in the sense of (9). 

When are any of the non-optimal sets contained in M actually optimal? In general we do not know. 

Since c effectively measures the quality of the sets in Lc,K the closer c is to 1, the closer the subsets 

are to optimal sets. A step towards answering this question would be to identify a class of graphs 

for which a moderate level of c is enough to guarantee that a large percentage of Lc,K consists of 

optimal and very high quality sets. 

3.1 The Graph of Optimal and Near Optimal Sets 

We introduce a graph G (Lc,K) whose nodes are the feasible sets of the greedoid described in Theorem 

1. To simplify the notation we use F = F(Lc,K) to denote the node set of G (Lc,K). The local 

structure of the graph is defined by adjacent nodes. 

Definition 4 Two nodes A and B∈ F are adjacent in G (Lc,K) if one of the following statements is 

true. 

• A, B ∈ F, B = A ∪ {r}, for r /∈ A 

• B = A \ a for some element a ∈ A 

• |A| = |B| and |A \ B| = 1 

Let A and C in F∩Lc,K be two feasible sets of equal cardinality. We assume the cardinality is greater 

than m,the smallest set in Lc,K. For some a ∈ V , the set D = A \ a is ∈ Lc,K. Indeed, since A is 

feasible, for some a, D is feasible. Moreover |D| ≥ m. By Theorem 1, any set of this cardinality is a 

member of Lc,K. Feasible sets of cardinality greater than m that are described in Corollaries 1 and 

2 have the property that there is a d ∈ C, not in A, such that B = D ∪ {d} ∈ F. For such greedoids, 

sets A and B and D are adjacent in G (Fc,K) where clearly B is the result of replacing a by d in A. 

By repeated swapping and other local moves, one can construct a neighborhood of A suitable for 

local search. When A is a subset of vertices of a feasible maximal match or vertex cover, navigation 

to an enlarged neighborhood can be achieved by a sequence of moves to feasible adjacent sets. In 

fact optimal sets that are not subsets of the vertex cover can be reached. In section 2.3, this is 

demonstrated using a different type of path than the one discussed here. A topic for future research 

is the development of efficient methods for doing this calculation as well as navigating G (Lc,K ) so 

that the number of evaluations of F is minimized. 

4 Conclusion 

We posed the problem of identifying the subset of nodes in a network that will enable the fastest 

spread of information in a decentralized communication environment. In a model of communication 

based on a random walk on an undirected graph G = (V, E), the optimal set of nodes are found 

by minimizing the sum of the mean times of first arrival to the set by walkers who start at nodes 

outside the set. 

12 
Since the objective function for this problem is supermodular, the greedy algorithm has been a 

principal method for constructing approximations to optimal sets. References [3], [1] obtain results 

guaranteeing that these sets are in some sense within (1 − 1/e) of optimality. In this work we took 

a different approach. Rather than seek an optimizing set for problem (4) without any information 

about G other than its cardinality and objective function F– the problem was reformulated. 

We introduced the concept of optimal and near optimal set, ordering the feasible subsets of 

problem (4) with a ranking relative to the vertex cover of the graph with cardinality K. A constant 

c is a lower bound on the rank that measures the degree of optimality of the sets (see equation 

(9)). For a fixed cardinality, higher ranking subsets are close to optimal solutions of the problem 

and approximations to the problem can be compared. If we want to improve an approximation we 

need a set structure to enable us to make local moves from one set to another. In particular, it 

should be possible to add, delete or swap elements so that the resulting set is still optimal or near 

optimal with the specified degree of optimality c. Our main result (Theorem 1, section 3), describes 

sufficient conditions for the construction of a greedoid based on selected optimal and near optimal 

subsets of smallest cardinality. This greedoid provides the desired structure for local search methods. 

A greedoid graph formalizes this idea as described in section 3.1. We believe that a local search 

method based on branch and bound is a promising avenue for current and future research ([5]). As 

seen in section 2.3 there are graphs where it is possible to improve the bounds guaranteed by the 

use of the greedy algorithm. As a corollary of our work we prove a theorem that gives sufficient 

conditions for when a vertex cover contains a near optimal subset, thereby partially confirming 

empirical observations made in section 2.1. 

Other issues for additional future research are characterizing the class of graphs for which this 

approach works well, i.e. when can sets with a high degree of optimality in the sense of problem (4) 

be achieved when we have a large c ? Finally the methods of this paper could be used to optimize 

submodular, monotone functions that arise in other models of network spread. For example it would 

be interesting to consider the independent cascade model discussed by Kempe et al. ([8]). 

References 

[1] V.S. Borkar, J. Nair, N. Sanketh, Manufacturing Consent, 48th Annual Allerton Conference, 

Allerton House, UIUC, Illinois, September 2010, pp. 1550-1555 

[2] A. Bjorner, G. Ziegler, Introduction to Greedoids, in Matroid Applications (ed. N. White), Encyclopedia of Mathematics, Vol. 40, Cambridge University Press, London, UK, 1992, pp.284-357 

[3] A. Clark, L. Bushnell, R. Poovendran, Leader Selection for Minimizing Convergence Error 

in Leader-Follower Systems:A Supermodular Optimization Approach, 10th International 

Symposium Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt), 

May 2012, pp. 111-115 

[4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, third edition, 

MIT Press, 2009 

[5] F.Hunt, Branch and Bound Methods for Calculating Optimal and Near Optimal sets in Consensus Models, preprint 2014 

13 
Figure 1: graph for EXAMPLE 1 with 9 vertices showing optimal K=1 set 

Figure 2: graph for EXAMPLE 1 with 9 vertices showing optimal K=2 set 

14
Figure 3: graph for EXAMPLE 1 with 9 vertices showing optimal K=3 set 

15
Figure 4: graph for EXAMPLE 1 with 9 vertices showing optimal K=4 set 

Figure 5: graph for EXAMPLE 1 with 9 vertices showing optimal K=5 set 

16
Figure 6: graph for EXAMPLE 2 with 6 nodes is shown with two vertex covers. The nodes of the 

covers are colored. On the left, the vertex cover contains no optimal subsets except itself, the vertex 

cover shown on the right contains optimal subsets for K = 1 through 4 

[6] D. Jungnickel, Graphs, Networks, and Algorithms, Springer Verlag, New York, Berlin, Heidelberg, Tokyo, 1991 

[7] J. Kemeny, J. Snell, Finite Markov Chains, 2nd edition, Springer-Verlag, New York, Berlin, 

Heidelberg, Tokyo, 1976 

[8] D. Kempe, J.. Kleinberg, E. Tardos, Maximizing the Spread of Influence through a Social 

Network, Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003 

[9] B. Korte, L. Lovasz, R. Schrader, Greedoids, Algorithms and Combinatorics Series, Vol. 4, 

Springer Verlag, Berlin, Germany,1991 

[10] R. Lambiotte, R. Sinatra, J.C.Delvenne, T.S. Evans, M. Barahona, V.Lattora, Interweaving 

dynamics and structure, Phys Rev. E 84, 017102, 2011 

[11] G.L. Nemhauser, L.A. Wolsey, M.L. Fisher, An analysis of approximations for maximizing 

submodular set functions-I, Mathematical Programming, Vol. 14, pp.553-574, 2003 

[12] C. Papadimitrioius, D. Steiglitz, Combinatorial Optimization and Complexity, Chapter 17 and 

p.432, Dover Publications, 1998 

17