Discrete Preference Games in Heterogeneous Social
Networks
Subverted Majorities and the Swing Player

arXiv:1603.02971v1 [cs.GT] 9 Mar 2016

Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli,
Clemente Galdi, and Giuseppe Persiano
Abstract
We study discrete preference games in heterogeneous social networks. These games model the
interplay between a player’s private belief and his/her publicly stated opinion (which could be different
from the player’s belief) as a strategic game in which the players’ strategies are the opinions and
the cost of an opinion in a state is a convex combination through a parameter α ∈ [0, 1] of two
factors: the disagreement between the player’s opinion and his/her internal belief and the number of
neighbors whose opinions differ from the one of the player. The parameter α models how stubborn
a player is: players with large α change their opinion only if many neighbors disagree with his/her
belief. We consider social networks that are heterogeneous in the sense that the parameter α can
vary from player to player.
We ask whether decisions made by a social network are robust to internal pressure and investigate
the phenomenon by which, because of local strategic decisions at the level of the players, the global
majority can be subverted. More precisely, we ask if it is possible that the belief shared by the majority
of the players does not coincide with the opinion that is publicly announced by the majority of the
players in an equilibrium state.
Our main result is a characterization of the social networks that admit an initial belief assignment
for which there exists a sequence of best response moves that reach an equilibrium in which the initial
majority is subverted. Our characterization is effective in the sense that can be tested efficiently and
the initial belief assignment that can be subverted can be computed in time polynomial in the number
of players. Our result is actually stronger as we show that in each initial belief assignment that can
be subverted, subversion is actually obtained in a very strong way: there exists one player, the swing
player, that changes his/her opinion to improve his/her utility and, as a result of this best response
move, every subsequent sequence of best response moves of the other players leads to an equilibrium
in which majority is subverted. In other words, it only takes one move of the swing player to lead
the social network to a point of no return in which any rational move from any player leads to a
subverted majority.

1

Introduction

Social networks play a crucial role in the way individuals form their opinions every day. Just to name few
examples, a recruiter interviewing a job-seeker can be influenced by the opinion that coworkers expressed
on Facebook or LinkedIn; a tourist looking for a restaurant can be influenced on the opinion read on
Yelp or TripAdvisor; a traveler looking for a hotel is influenced by the opinion given by his friends on
Booking.com.
Several models have been introduced in order to model how agent react to this influence and how
the opinions are formed. A first natural model is given by majority dynamics: each agent has an initial
preference and at each time step a subset of players updates their opinion to the one expressed by the
majority of their neighbors. Another classical model has been proposed by DeGroot [4], and later refined
by Friedkin and Johnsen [6]. The model assumes that each agent has a private belief, but the public
opinion she eventually expresses can be different from her belief. In particular, the opinion comes out
from a repeated averaging between the belief and the opinions of individuals with whom she has social
relations. A similar model, that is more suitable for the case in which beliefs and opinions are discrete,
assumes that each agent behaves strategically and aims to pick the most beneficial (or less costly) opinion
1

for her, where the benefit (or cost) depends both on her internal belief and on the opinions of individuals
with whom she has social relations. This model has been recently adopted by Ferraioli et al. [5] and by
Chierichetti et al. [3], that considered the case of binary beliefs or opinions1 .
Our setting. In this paper we consider binary discrete preference games with n players. A discrete
preference game consists of a n-vertex undirected graph G (the social network), stubbornness levels
α1 , . . . , αn ∈ (0, 1) and beliefs b(1), . . . , b(n) ∈ {0, 1}. The players are identified with the vertices of G
and each player i has a stubbornness level αi ∈ (0, 1) and a belief b(i) ∈ {0, 1}. Player i can choose to
play opinion s(i) ∈ {0, 1} and the cost ci (s) of agent i in state s = (s(1), . . . , s(n)) ∈ {0, 1}n is defined
as
X
|s(i) − s(j)|,
(1)
ci (s) = αi · |s(i) − b(i)| + (1 − αi ) ·
j∈N (i)

where N (i) is the set of neighbors of vertex i in G (i.e., friends in the social network). Note that the cost
is the convex combination through αi of two components that depend on whether the opinion coincides
with the belief and on the strategies of the neighbors, respectively. The stubbornness level αi measures
the weight given by player i to her own belief. Roughly speaking, high values of αi are associated with
players that need a lot of convincing from their friends to change their mind and adopt an opinion in
contrast with their beliefs.
We consider the game starting in the truthful state in which s(i) = b(i) for all i and then evolving
through a set of sequential best response moves until an equilibrium is reached. We define an equilibrium
state to be a state s = (s(1), . . . , s(n)) for which there is no player i whose best response is to adopt
strategy 1 − s(i). More precisely, s is an equilibrium if for all i
ci (s) ≤ ci ((s−i , 1 − s(i))),
where we have used the standard game theoretic notation by which (s−i , a) denotes the vector
(s−i , a) = (s(1), . . . , s(i − 1), a, s(i + 1), . . . , s(n)).
Obviously, the strategic moves of the player affect the way the network works and evolves. Hence,
in order to get an insight about how we can improve the performance of the social network, we need
to understand at which extent the behavior of network’s members may affect the system at large. Is it
possible that the local behavior of the players affect the global behavior of the network? Does the social
pressure felt by individual members of a social networks have any effects on the entire network?
In this paper we take the behavior of a network to be the majority of the opinions expressed by
its members once the network has reached an equilibrium state. We ask whether it is possible that the
majority of the opinions differ from the majority of the belief. In other words, is it possible that majority
can be subverted by social pressure?
Our contribution. We say that a pair (G, (α1 , . . . , αn )) consisting of a graph G with n vertices (we
assume n odd so that majority is well defined) and of the sequence of stubbornness levels is subvertable
if there exists a belief assignment (b(1), . . . , b(n)) with a majority of 0 and a sequence of best response
moves that goes from the truthful state to an equilibrium state with a majority of 1. We call such a
belief assignment subvertable.
Our main contribution is a characterization of the subvertable pairs. Roughly speaking, our characterization says that a pair is subvertable unless all players are stubborn. More precisely, consider vertex x
with bx = 0 and d0 neighbors with opinion 0 and d1 neighbors with opinion 1. Then the cost of opinion
0 for x is (1 − αx )d1 whereas the cost of opinion 1 is αx + (1 − αx )d0 . Therefore x has an incentive to
αx
declare opinion 1 iff d1 − d0 ≥ ax + 1, where ax = ⌊ 1−α
⌋. Clearly, this cannot happen if the degree
x
d(x) = d1 + d0 of x satisfies d(x) ≤ ax . Suppose now the majority (that is at least (n + 1)/2 vertices)
have belief 0 and thus d1 ≤ (n − 1)/2. If d(x) ≥ n − ax − 1 then
d1 − d0 = 2d1 − d(x) ≤ n − 1 − d(x) ≤ ax
1 Chierichetti et al. [3] also consider the case of multiple beliefs/opinions. Still, in this case multiple metrics can be
considered for evaluating the distance among opinions, and different metrics embeds a very different behavior of people in
social networks.

2

and thus vertex x does not have an incentive to declare opinion 1. The same reasoning applies for vertices
x with bx = 1 in case majority is 1. We have thus the following definition.
Definition 1 (Stubborn vertex). A vertex x with degree d(x) and stubbornness αx is stubborn if


αx
ax :=
≥ min {d(x), n − d(x) − 1} .
1 − αx
Clearly, if all vertices are stubborn then majority cannot be subverted as no vertex has an incentive
to play an opinion be different from the belief. The main result of this paper shows that
if there exists at least one non-stubborn vertex then there exists a subvertable belief assignment.
A possible interpretation of our result is that social networks are extremely vulnerable to social pressure
since there always exists a subvertable majority unless all vertices are stubborn and never change their
mind (in which case we do not have much of a social network). This is particularly negative as an
external adversary might be able to orchestrate the sequence of best response moves so to reach the state
in which majority is subverted. In principle, though, this could be very difficult since there could be
different sequences of best response moves that lead to different equilibria with different majorities and
the adversary has to be very careful in scheduling the best response moves. Our characterization instead
proves that there is always one single swing player whose best response in the truthful state is to change
her opinion and this leads the social network to a state in which any sequence of best response moves
leads to an equilibrium in which majority has been subverted. In other words, the adversary that wants
to subvert the majority only has to influence the swing player and then the system will evolve without
any further intervention towards an equilibrium in which majority is subverted. More precisely,
Definition 2. A vertex u is said to be a swing vertex for subvertable belief assignment b with
vertices with belief 0 if

n+1
2

1. b(u) = 0;
2. cu (b) > cu (b′ ), where b′ = (b−u , 1)).
That is, in the truthful state, u’s best response is to play opinion 1.
3. For every x with b(x) = 1, it holds that cx (b′ ) ≤ cx (0, b′−x ).
That is, after u’s best response no vertex with belief 1 has an incentive to change her opinion.
Note that definition above does not imply that the majority at equilibrium consists of only n+1
2
vertices with belief 1 (the initial n−1
plus the swing vertex). It may be indeed the case that other
2
vertices with belief 0 have an incentive to change their opinion after the swing vertex’s best response
move. Still, the definition of swing vertex assures that, after her best response, the number of vertices
with opinion 1 is a majority and the size of this majority does not decrease.
Our main result can be improved as follows
if there exists at least one non-stubborn vertex then there exists a subvertable belief assignment with a
swing vertex.
It is natural to ask whether the characterization can be strengthened to take into account strong
majorities (that is, majorities of size at least (1 + δ) n+1
2 for some 0 < δ < 1). That is, to characterize the
pairs (consisting of a social network and stubbornness levels) that admit at least a subvertable strong
majority. We prove that no such characterization can be given by showing that there exists δmax ≈ 0, 85
such that for all 0 < δ < δmax it is NP-hard to decide whether a given G and given stubbornness levels
α1 , . . . , αn admit a subvertable majority of size at least (1 + δ) n+1
2 .
Previous work. Our work is strictly related with a line of work in social sciences that aims to understand how opinions are formed and expressed in a social context. A classical simple model in this
context has been proposed by Friedkin and Johnsen [6] (see also [4]). Its main assumption is that each
individual has a private initial belief and that the opinion she eventually expresses is the result of a
repeated averaging between her initial belief and the opinions expressed by other individuals with whom
3

she has social relations. The recent work of Bindel et al. [2] assumes that initial beliefs and opinions
belong to [0, 1] and interprets the repeated averaging process as a best-response play in a naturally
defined game that leads to a unique equilibrium.
Discrete belief and opinions have been first considered in [5] that studied rate of convergence of the
game under different dynamics and in [3] that were mainly interested in the price of stability and price
of anarchy of the games. In a previous paper [1], the authors have studied subvertable majorities for
the majority dynamics in which players adopt the majority of the opinions expressed by the neighbors
and uses their private belief only as a tie breaker. This dynamics corresponds to the special case of
homogeneous networks in which for all x, αx = α for some α < 1/2.
Notation. For subsets A, B ⊆ V of the vertices of G we denote by W (A, B) the number of edges with
one endpoint in A and the other in B. If A = {x} is a singleton, we will simply write W (x, B); similarly
for B. Thus, for vertices x, y, W (x, y) = 1 if and only if x and y are adjacent.

2

Definitions and Technical Overview

In this section we introduce the concepts of a bisection and of a good bisection and give an overview of
the proof.
Good bisections yield subvertable belief assignments. A bisection S = (S, S) of a graph G with
an odd number n of vertices is a partition of the vertices of G into two sets S and S of cardinality n+1
2
and n−1
,
respectively.
We
define
the
deficiency
def
(x)
of
a
vertex
x
with
respect
to
bisection
S
=
(S,
S)
S
2
as follows:
(
W (x, S) − W (x, S), if x ∈ S;
def S (x) =
W (x, S) − W (x, S), if x ∈ S.
We say that a bisection S = (S, S) is good if
1. for every x ∈ S, def S (x) ≥ −ax ;
2. there is u ∈ S with def S (u) ≥ au + 1.
Vertices u ∈ S with def S (u) ≥ au + 1 are called the good vertices of S and vertices y ∈ S with
def S (y) < −ay are called the obstructions of S 2 . Next lemma proves that if G has a good bisection then
one can easily construct a subvertable belief assignment for G.
Lemma 1. Let S = (S, S) be a good bisection for graph G and let u be one of its good vertices. Then G
admits a subvertable belief assignment b such that u is a swing vertex for b.
Proof. Consider the belief assignment b such that b(x) = 1 for every x ∈ S \ {u} and b(x) = 0 for every
x ∈ S ∪ {u}. Thus, in the truthful profile b there is a majority of vertices with opinion 0.
Now, consider vertex u. Since S is good and u is a good vertex for S,
def S (u) = W (u, S) − W (u, S) ≥ au + 1 >

αu
.
1 − αu

The cost of u in the truthful state b is cu (b) = (1 − αu )W (u, S); if u plays opinion 1 instead the cost is
cu ((b−u , 1)) = αu + (1 − αu )W (u, S). It follows that cu (b) − cu ((b−u , 1)) = (1 − αu )def S (u) − αu > 0.
Then it is a best-response for u to adopt opinion 1.
Let b′ = (1, b−u ), i.e., the profile reached after the best-response of u. Note that in b′ there is
a majority of vertices with opinion 1. We prove that no vertex x with opinion 1 (that is, no vertex
x ∈ S) has an incentive to change her opinion, from which we can conclude that b is a subvertable belief
assignment and u is a swing vertex for b.
This is obvious for x = u. Since S is good, then, for every x ∈ S,
def S (x) = W (x, S) − W (x, S) ≥ −ax ≥ −
2 We

remind the reader that, for vertex x, we set ax =

j

αx
1−αx

4

k
.

αx
.
1 − αx

As for x 6= u, the cost of x in state b′ = (b−u , 1) is cx (b′ ) = (1 − αx )W (x, S) whereas the cost of x in
b′′ = (b′−x , 0) is cx (b′′ ) = αx +(1−αx )W (x, S). It follows that cx (b′′ )−cx (b′ ) = (1−αx )def S (x)+αx ≥ 0
and, thus, x has no incentive to adopt opinion 0.
Minimal bisections. The technical core of our proof is the construction of a good bisection starting
from a bisection S of minimal potential Φ. We define the potential Φ of a bisection (S, S) as


X
1 X
ay  .
ax −
Φ(S, S) = W (S, S) +
2
x∈S

y∈S

We say that a bisection S has k-minimal potential if S minimizes the potential among all the bisections
that can be obtained from S by swapping at most k vertices between S and S. That is, S has k-minimal
potential if, for all A ⊆ S and for all B ⊆ S, with 1 ≤ |A| = |B| ≤ k,
Φ(S, S) ≤ Φ(S \ A ∪ B, S \ B ∪ A).

We will simply write that S has minimal potential whenever S has 1-minimal potential.
Next lemmas prove some useful properties of minimal bisections.
Lemma 2. Let S = (S, S) be a bisection of minimal potential. Then for all x ∈ S and y ∈ S,
def S (x) + def S (y) + 2W (x, y) ≥ ax − ay .
Proof. Set A = S \ {x}, B = S \ {y}, T = A ∪ {y} and T = B ∪ {x}. Note that
1
Φ(T, T ) = W (A, B) + W (x, A) + W (y, B) + W (x, y) +
2

X

au −

X

u∈A

v∈B

X

X

av + ay − ax

!

and
1
Φ(S, S) = W (A, B) + W (x, B) + W (y, A) + W (x, y) +
2

u∈A

au −

av + ax − ay

v∈B

!

.

Since S has minimal potential we have
0 ≤ Φ(T, T ) − Φ(S, S) = W (x, A) + W (y, B) − W (x, B) − W (y, A) + ay − ax
= W (x, S) − W (x, S) + W (y, S) − W (y, S) + 2W (x, y) + ay − ax
= def S (x) + def S (y) + 2W (x, y) + ay − ax .
Swapping vertices. To turn a minimal bisection S into a good bisection T = (T, T ), we need at
least one vertex in T with high deficiency. One way to increase the deficiency of a vertex u ∈ S is to
move vertices that are not adjacent to u away from S and to bring the same number of vertices that are
adjacent to u into S. We define the rank of a vertex u with respect to bisection S as


au + 1 − def S (u)
.
rankS (u) =
2
Note that a vertex u of rankS (u) has deficiency def S (u) such that
au − 2rankS (u) + 1 ≤ def S (u) ≤ au − 2rankS (u) + 2.

(2)

It is not hard to see that the rank is exactly the number of vertices that need to be moved. We next
formalize the notion of swapping of vertices and prove that it is always possible to increase the deficiency
of a non-stubborn vertex x to ax .
Given a bisection S = (S, S) and a vertex u, a u-pair for S is a pair of sets (Au , Bu ) such that:
• if u ∈ S, then Au ⊆ S ∩ N (u) and Bu ⊆ S ∩ N (u) with |Au | = |Bu | = rankS (u);
5

• if u ∈ S, then Au ⊆ S ∩ N (u) and Bu ⊆ S ∩ N (u) with |Au | = rankS (u) and |Bu | = rankS (u) − 1.
The bisection T associated with the u-pair (Au , Bu ) for S is defined as
• if u ∈ S, T = (S \ Au ∪ Bu , S \ Bu ∪ Au );
• if u ∈ S, T = (S \ Bu ∪ Au , S \ Au ∪ Bu ).
The next lemma shows that a u is a good vertex in the bisection associated with a u-pair.
Lemma 3. For each bisection S, let u be a vertex of the graph, (Au , Bu ) a u-pair for S, and T the
bisection associated to (Au , Bu ). Then def T (u) ≥ au + 1.
Proof. Denote rankS (u) by ℓ and thus def S (u) ≥ au − 2ℓ + 1. If u ∈ S, then, by definition of u-pair,
W (u, Au ) = 0 and W (u, Bu ) = ℓ. Hence,
def T (u) = W (u, T ) − W (u, T )
= W (u, S) − W (u, S) − 2W (u, Au ) + 2W (u, Bu )
= def S (u) + 2ℓ ≥ au + 1.
If u ∈ S, then, by definition of u-pair, W (u, Au ) = ℓ and W (u, Bu ) = 0. Hence,
def T (u) = W (u, T ) − W (u, T )
= W (u, S) − W (u, S) + 2W (u, Au ) − 2W (u, Bu )
= def S (u) + 2ℓ ≥ au + 1.
Next lemma proves that, for every bisection S and every vertex u, a u-pair for S exists if and only if
vertex u is non-stubborn.
Lemma 4. For every bisection S = (S, S) and every vertex u, a u-pair for S exists if and only if u is
non-stubborn.
Proof. Suppose that u is a stubborn vertex and let (Au , Bu ) a u-pair for S. By Lemma 3, in the bisection
T associated with this u-pair, def T (u) ≥ au + 1. But this contradicts Lemma 5.
Consider now a non-stubborn u. Let us denote rankS (u) by ℓ. If u ∈ S, then it is sufficient to show
that
n+1
W (u, S) ≤
−ℓ
and
W (u, S) ≥ ℓ.
2
Indeed, we have
W (u, S) =

d(u) + def S (u)
2

and

W (u, S) =

d(u) − def S (u)
.
2

Since u is non-stubborn, we have au + 1 ≤ d(u) ≤ n − au − 2. Moreover, recall that def S (u) ≤ au − 2ℓ + 2.
Whence
(n − au − 2) + (au + 2 − 2 · ℓ)
n−2·ℓ
n+1
=
<
−ℓ
2
2
2
1
(au + 1) − (au + 2 − 2 · ℓ)
=ℓ− .
W (u, S) ≥
2
2

W (u, S) ≤

Since W (u, S) is an integer, then it must be the case that W (u, S) ≥ ℓ.
If u ∈ S, we instead need to show that
W (u, S) ≥ ℓ

and

W (u, S) ≤

n−1
− ℓ + 1.
2

A reasoning similar to the one above proves that these inequalities hold.
Hence, if T is the bisection associated to u-pair (Au , Bu ) for S, then u is certainly a good vertex for
T . Thus, if T is not good then there is a vertex y that is an obstruction for T . In the last case, we will
say that the vertex u, the u-pair (Au , Bu ) and the bisection T are obstructed by y.
6

Stubborn vertices cannot be obstructions. Next lemma says that stubborn vertices are sort of
neutral: they cannot be obstruction but they cannot be good either.
Lemma 5. For every bisection S = (S, S) and every stubborn vertex x ∈ S it holds that
−ax ≤ def S (x) ≤ ax .
Proof. By definition, x is stubborn if ax ≥ min {d(x), n − d(x) − 1}. The statement is obvious if ax ≥
d(x). Thus consider x ∈ S with d(x) ≥ ax ≥ n − d(x) − 1. From the definition of def S (x) and from the
fact that d(x) = W (x, S) + W (x, S) we obtain
W (x, S) =

d(x) + def S (x)
n − ax − 1 + def S (x)
≥
2
2

Since W (x, S) ≤ n+1
2 − 1, we obtain def S (x) ≤ ax .
Similarly, we have
n − ax − 1 − def S (x)
n−1
d(x) − def S (x)
≥ W (x, S) =
≥
2
2
2
whence we obtain def S (x) ≥ −ax .

3

Main theorem

Our main result is the following.
Theorem 1. Every graph G with an odd number of vertices and at least one non-stubborn vertex has
a subvertable belief assignment b and a swing vertex u for b. Moreover, b and u can computed in
polynomial time.
We prove the theorem by exhibiting a polynomial-time algorithm (see Algorithm 1) that, given a
graph G with an odd number of vertices, and at least one of which that is non-stubborn, returns a good
bisection S and a good vertex u for S. The theorem then follows from Lemma 1.
First, we note that the algorithm runs in time that is polynomial on the size of the input. Indeed, a
bisection of 3-minimal potential at Line 1 can be efficiently computed through a local search algorithm
[7], and all remaining steps only involve computationally easy tasks.
Next we prove that the algorithm is correct; that is, it outputs (T , u) where T is a good bisection
and u is a good vertex for T . Recall that, by Lemma 5, it is sufficient to check that def T (u) ≥ au + 1
and that non-stubborn vertices x ∈ S have def T (x) ≥ −ax .

3.1

Warm-up Cases

In this section we show that if Algorithm 1 stops before reaching Line 15 then it returns a good bisection
and a good vertex.
The algorithm stops at Line 5. In this case, T = (S ∪ {u}, S \ {u}) and def S (u) ≤ −au − 1. Since
u ∈ S, we have that def T (u) = −def S (u) ≥ au + 1. Moreover, for every non-stubborn x ∈ T , x 6= u,
def T (x) = def S (x)+2W (x, u). By applying Lemma 2 to u ∈ S and x ∈ S, we obtain def S (x)+2W (x, u) ≥
−def S (u) + au − ax . Therefore
def T (x) = def S (x) + 2W (x, u)
≥ −def S (u) + au − ax
≥ 2au + 1 − ax ≥ −ax .
The algorithm stops at Line 7. In this case all vertices x ∈ S have def S (x) ≥ −ax (for otherwise
the algorithm would have stopped at Line 5) and u is a good vertex.

7

1
2

3
4
5
6
7
8
9
10
11
12
13
14

15
16

17
18

Input: A graph G with an odd number of vertices and at least one non-stubborn vertex
Output: A pair (S, u) where S is a good bisection and u is its good vertex
Compute a bisection S = (S, S) of G of 3-minimal potential
Let M be the set of non-stubborn vertices of minimum rank in S
/* Warm-up cases */
if there is u ∈ S with def S (u) ≤ −au − 1 then
Let T = (S ∪ {u}, S \ {u})
return (T , u)
if there is u ∈ S with def S (u) ≥ au + 1 then
return (S, u)
if there is u ∈ S with def S (u) ≥ au + 1 then
Pick w ∈ S and let T = (S ∪ {w}, S \ {w})
return (T , u)
if there is u ∈ S ∩ M with def S (u) < 0 then
Let S ′ = (S ∪ {u}, S \ {u})
Pick u-pair (Au , Bu ) for S ′ and let T be the associated bisection
return (T , u)
/* There is a non-stubborn vertex of minimal rank in S */
if M ∩ S 6= ∅ then
return MinRankInNotS(S)
/* All non-stubborn vertices of minimal rank are in S */
else
return MinRankInS(S)
Algorithm 1: Algorithm for computing a good bisection and its good vertex

The algorithm stops at Line 10. In this case we have that T = (S ∪ {w}, S \ {w}) and it must be
the case that −ax ≤ def S (x) ≤ ax for every x ∈ S (for otherwise the algorithm would have stopped at
an earlier step) and there is u ∈ S with def S (u) ≥ au + 1.
Now, def T (w) = −def S (w) ≥ −aw and def T (u) = def S (u) + 2W (u, w) ≥ au + 1. Moreover, for every
non-stubborn vertex y ∈ T , we have def T (y) = def S (y) + 2W (y, w). By applying Lemma 2 to w ∈ S and
to y ∈ S, we obtain that def S (y) + 2W (y, w) ≥ −def S (w) + aw − ay and therefore we can write
def T (y) = def S (y) + 2W (y, w) ≥ −def S (w) + aw − ay ≥ −ay ,
since we have def S (w) ≤ aw .
The algorithm stops at Line 14. In this case we have that T = (S ∪ {u} \ Au ∪ Bu , S \ {u} ∪ Au \ Bu )
and let us denote rankS (u) by ℓ.
Since T is the bisection associated to a u-pair, then, by Lemma 3, def T (u) ≥ au + 1. Moreover,
def S ′ (u) = −def S (u) (where S ′ is defined at Line 12) and therefore
 


au + 1 + def S (u)
au + 1 − def S ′ (u)
=
rankS ′ (u) =
2
2


au + 1 − def S (u)
=
+ def S (u) = rankS (u) + def S (u) ≤ ℓ − 1.
2
For every non-stubborn x ∈ T with x 6= u we have that
def T (x) = W (x, S) − W (x, S) + 2W (x, u) − 2W (x, Au ) + 2W (x, Bu ).
If x ∈ S \ Au , then
def T (x) = def S (x) + 2W (x, u) − 2W (x, Au ) + 2W (x, Bu )
≥ def S (x) + 2W (x, u) − 2|Au | = def S (x) + 2W (x, u) − 2rankS ′ (u)
≥ def S (x) + 2W (x, u) − 2ℓ + 2.
8

By applying Lemma 2 to x ∈ S and u ∈ S, we obtain def S (x) + 2W (x, u) ≥ −def S (u) + au − ax and,
from (2), we obtain def S (u) ≤ ax − 2ℓ + 2. Hence def T (x) ≥ −ax .
Finally, let us consider x ∈ Bu . Then x ∈ S and we have
def T (x) = −def S (x) + 2W (x, u) − 2W (x, Au ) + 2W (x, Bu )
≥ −def S (x) − 2W (x, Au ) ≥ −def S (x) − 2ℓ + 2.
However, by hypothesis u has minimum rankS (u) among the non-stubborn vertices and thus it must be
the case that rankS (x) ≥ rankS (u) which implies that def S (x) ≤ ax + 2 − 2ℓ. Therefore, def T (x) ≥ −ax .

3.2

Properties of the obstructions

Most of the work in the remaining cases will be devoted to deal with obstructions. Therefore, before to
proceed, we prove some their useful properties.
Lemma 6. Let u ∈ S be a vertex of minimum rank for the bisection S and let y be an obstruction for
u. Then y ∈ S. Similarly, let u ∈ S be a vertex of minimum rank for the bisection S and assume there
is no vertex of minimum rank in S. If y is an obstruction for u, then y ∈ S.
Proof. Suppose y is an obstruction for the bisection T associated to u-pair (Au , Bu ) and let rankS (u) = ℓ.
We proceed by contradiction. Suppose first that y ∈ S and u ∈ S. Since u is a vertex of minimum
rank, it must be the case that rankS (y) ≥ ℓ and thus, by (2), def S (y) ≤ ay + 2 − 2ℓ. Then, it holds that
def T (y) = W (y, S) − W (y, S) + 2W (y, Au ) − 2W (y, Bu )
≥ −def S (y) − 2W (y, Bu )
≥ −def S (y) − 2 · (ℓ − 1) ≥ −ay .
This is a contradiction, because y is an obstruction for T and def T (y) < −ay .
Suppose now that y ∈ S and u ∈ S. Since there are no vertices of minimum rank in S, then
rankS (y) ≥ ℓ + 1 and thus, by (2), def S (y) ≤ ay − 2ℓ. Then, it holds that
def T (y) = W (y, S) − W (y, S) − 2W (y, Au ) + 2W (y, Bu )
≥ −def S (y) − 2W (y, Au )
≥ −def S (y) − 2ℓ ≥ −ay .
As above, this contradicts that y is an obstruction for T .
Lemma 7. Let S be a bisection and let u be a vertex of minimum rank in S. Let T be the bisection
associated with a u-pair (Au , Bu ) for S. If vertex y is an obstruction for T , then
def S (y) ≤ −ay + 2rankS (u) − 3.
Moreover, for every non-stubborn v ∈ S if
def S (v) + def S (y) + 2W (v, y) ≥ av − ay ,
then v and y are adjacent, v has minimum rank and
def S (y) ≥ −ay + 2rankS (u) − 4.
Proof. Let ℓ be the minimum rank with respect to the bisection S.
Since u ∈ S, by Lemma 6, y ∈ S. Moreover, its deficiency is such that
−ay > def T (y) = def S (y) + 2W (y, Au ) − 2W (y, Bu ) ≥ def S (y) − 2|Bu | = def S (y) − 2(ℓ − 1),
from which we obtain that
def S (y) ≤ −ay + 2ℓ − 3.

9

(3)

For every non-stubborn vertex v ∈ S that satisfies (3), we have that rankS (v) ≥ ℓ, and thus, by (2),
def S (v) < av − 2ℓ + 3. Then
−ay + 2ℓ − 3 ≥ def S (y) ≥ −def S (v) − 2W (v, y) + av − ay
> −ay + 2ℓ − 3 − 2W (v, y),
from which we obtain that W (v, y) = 1 and def S (y) ≥ −ay + 2ℓ − 4. Moreover, from Lemma 2,
def S (v) ≥ −def S (y) − 2W (v, y) + av − ay
≥ ay − 2ℓ + 3 − 2 + av − ay
= av − 2ℓ + 1,
and this implies that rankS (v) ≤ ℓ. But, since ℓ is the minimum rank with respect to S, then rankS (v) =
ℓ.
Lemma 8. Let S be a bisection and suppose that there is no vertex in S with minimum rank. Let u be
a vertex of minimum rank in S. Let T be the bisection associated with a u-pair (Au , Bu ) for S. Suppose
there is an obstruction y for T with def S (y) < 0 and rankS (y) > rankS (u). Let S ′ = (S ∪ {y}, S \ {y}).
Then rankS ′ (y) ≤ rankS (u).
Proof. Let rankS (u) = ℓ. Therefore rankS (y) > ℓ and thus def S (y) ≤ ay − 2ℓ. Moreover, since by
Lemma 6, def S ′ (y) = −def S (y) and thus
 


ay + 1 + def S (y)
ay + def S (y)
ay + 1 − def S ′ (y)
+ 1.
(4)
=
≤
rankS ′ (y) =
2
2
2
Since y is an obstruction for T
−ay > def T (y) = def S (y) − 2W (y, Au ) + 2W (y, Bu ) ≥ def S (y) − 2ℓ,
where we used that W (y, Au ) ≤ |Au | = ℓ. Hence, ay + def S (y) < 2ℓ and, by plugging this in (4), we
obtain rankS ′ (y) ≤ ℓ.
Lemma 9. Let S be a bisection and let u be a vertex of minimum rank in S. Let T be the bisection
associated with a u-pair (A
lu , Bum) for S. Suppose there is an obstruction y for T with def S (y) ≥ 0. Then
a +1
and def S (y) = 0.
y has minimum rank ℓ = y2

Proof. Let rankS (u) = ℓ. We start by observing that

def T (y) = def S (y) − 2W (y, Au ) + 2W (y, Bu )
≥ def S (y) − 2ℓ.
Since y is an obstruction for T , it must be that def T ≤ −(ay + 1) and thus, since def S (y) ≥ 0, we have
a +1
that ℓ ≥ y2 .
On the other side, since rankS (y) ≥ ℓ, we have that
0 ≤ def S (y) ≤ ay + 2 − 2ℓ,
from which we obtain the

ay +1
2

≤ℓ≤

ay
2
ay
2

+ 1. Since ℓ is an integer, it follows that ℓ =

(5)
l

ay +1
2

m

.

Now, if ay is even (and thus ℓ =
+ 1), then, by (5), we obtain def S (y) = 0. Moreover, since
0 ≥ ay − 2ℓ + 1, y has minimum rank ℓ.
a +1
If ay is odd (and thus ℓ = y2 ), then, by (5), we obtain 0 ≤ def S (y) ≤ 1. If def S (y) = 1 then
def T (y) = def S (y) − 2W (y, Av ) + 2W (y, Bv ) ≥ 1 − 2ℓ = −ay ,
which contradicts the fact that y is an obstruction for T . Hence def S (y) = 0 and, since 0 ≥ ay − 2ℓ + 1,
y has minimum rank.

10

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

MinRankInNotS(S):
for every u ∈ S ∩ M do
for every v ∈ S ∩ N (u) ∩ M do
Pick a u-pair (Au , Bu ) for S with v ∈ Au and let T be the associated bisection
if T is good then
return (T , u)
Let y be an obstruction for one of the bisections T defined at Line 4
if there is non-stubborn v ∈ S then
Pick a v-pair (Av , Bv ) for S with y ∈ Bv and let T be the associated bisection
return (T , v)
Pick a vertex w ∈ S ∩ N (y) and let S ′ = (S \ {w} ∪ {y}, S \ {y} ∪ {w})
Pick a y-pair (Ay , By ) for S ′ and let T be the associated bisection
return (T , y)
Algorithm 2: There is a non-stubborn vertex of minimal rank in S

3.3

There is a non-stubborn vertex of minimal rank in S

Consider now the case that there is a non-stubborn vertex u ∈ S of minimum rank. We then execute
the procedure MinRankInNotS (see Algorithm 2). If MinRankInNotS stops at Line 6, then clearly the
returned bisection is good and, since the bisection is associated with a u-pair, then, by Lemma 3, u is a
good vertex for it.
MinRankInNotS stops at Line 10. In this case, y is an obstruction for a vertex u ∈ S of minimum
rank, and thus, by Lemma 6, y belongs to S. Moreover, there is at least one non-stubborn vertex in
S. Observe that, since S has minimal potential, from Lemma 2 it follows that for every non-stubborn
vertex x ∈ S
def S (x) + def S (y) + 2W (x, y) ≥ ax − ay .
Thus, by Lemma 7, y and v are adjacent, where v is the vertex considered at Line 9. Therefore it is
possible to pick a v-pair (Av , Bv ) with y ∈ Bv .
Since T is the bisection associated with a v-pair, by Lemma 3, def T (v) ≥ av + 1. Thus, we only
need to prove that def T (x) ≥ −ax for every non-stubborn x ∈ T . First note that, by Lemma 7, v has
minimum rank and we denote rankS (v) by ℓ. Moreover, for all non-stubborn vertices x ∈ T we have
def T (x) = W (x, S) − W (x, S) − 2W (x, Av ) + 2W (x, Bv ).
For non-stubborn x ∈ Bv , we have def S (x) = W (x, S) − W (x, S) and thus
def T (x) = −def S (x) − 2W (x, Av ) + 2W (x, Bv ) ≥ −def S (x) − 2ℓ
We next prove that def S (x) ≤ ax − 2ℓ and thus def T (x) ≥ −ax . Suppose by contradiction that def S (x) ≥
ax − 2ℓ + 1. Therefore, by (2), x is a non-stubborn vertex of S of minimum rank ℓ and thus the for-loop
starting at Line 2 has considered a bisection T ′ associated with an x-pair (Ax , Bx ) for S with v ∈ Ax
that admitted an obstruction y ′ . Note that, by Lemma 6, y ′ ∈ S. Then
def T ′ (y ′ ) = W (y ′ , S) − W (y ′ , S) + 2W (y ′ , Ax ) − 2W (y ′ , Bx )
≥ def S (y ′ ) + 2W (y ′ , v) − 2|Bx |.
Since |Bx | = ℓ − 1 and, by Lemma 7, def S (y ′ ) ≥ −ay′ + 2ℓ − 4 and W (y ′ , v) = 1, we have that
def T ′ (y ′ ) ≥ −ay′ . This is a contradiction, because y ′ is an obstruction for T ′ .
We conclude the proof by considering non-stubborn x ∈ S \ Av , x 6= v. For such a vertex we have
def T (x) = def S (x) − 2W (x, Av ) + 2W (x, Bv ) ≥ def S (x) − 2ℓ + 2
where we used that, according to Lemma 7, x and y are adjacent and, by construction, y ∈ Bv . It is thus
sufficient that def S (x) ≥ −(ax − 2ℓ + 2). Note that, by Lemma 7, rankS (x) = ℓ and thus minimal. Hence,
it must be the case that def S (x) ≥ 0 (otherwise the algorithm stops at Line 14) and def S (x) ≤ ax −2ℓ+2.
Thus ax − 2ℓ + 2 ≥ 0 and then def S (x) ≥ −(ax − 2ℓ + 2), as desired.
11

MinRankInNotS stops at Line 13. Since the algorithm has not stopped before reaching this line, then
in S there is a non-stubborn vertex of minimal rank, and every vertex of S is stubborn. Before proving
that T is a good bisection, we show that there exists at least one vertex w ∈ S that is not adjacent to
obstruction y defined at Line 7 and thus T can be constructed.
We proceed by contradiction and assume that y is adjacent to every vertex of S. Recall that, by
Lemma 6, y ∈ S. Then, by applying Lemma 2 to any z ∈ S and to y we obtain that
def S (y) ≥ −def S (z) − 2W (z, y) + az − ay ≥ −ay − 2,
where we used that z is stubborn and thus, by Lemma 5, def S (z) ≤ az . Remember that y is an
obstruction for u-pair (Au , Bu ) where u ∈ S is a vertex of minimum rank ℓ. Let us denote by T ′ the
bisection associated with this u-pair. We have that
def T ′ (y) = def S (y) + 2W (y, Av ) − 2W (y, Bv )
≥ −ay − 2 + 2W (y, Av ) − 2W (y, Bv )
≥ −ay − 2 + 2W (y, Av ) − 2(ℓ − 1)
Since y is adjacent to all vertices of S then W (y, Av ) = |Av | = ℓ, and thus def T ′ (y) ≥ −ay . This is a
contradiction, as y is an obstruction for T ′ . We have thus established that y is not adjacent to all the
vertices in S and thus the algorithm can pick vertex w at Line 11.
Since T is the bisection associated to a y-pair, then, by Lemma 3, def T (y) ≥ ay + 1. Thus, we only
need to prove that def T (x) ≥ −ax for every non-stubborn x ∈ T . Consider the bisection S ′ defined at
Line 11. Note that def S ′ (y) = −def S (y) and

 

ay + 1 − def S ′ (y)
ay + 1 + def S (y)
rankS ′ (y) =
=
≤ ℓ − 1,
2
2
where in the last inequality we used that, by Lemma 7, def S (y) ≤ −ay + 2ℓ − 3.
Let (Ay , By ) be the y-pair defined at Line 12. Since all vertices in S are stubborn, then the only
non-stubborn vertices in T different from y belong to By ⊆ S \ {y} ∪ {w}. For every such vertex x,
we have that, by minimality of ℓ, def S (x) ≤ ax − 2ℓ + 2, W (x, y) = 1. Moreover, W (x, w) ≤ 1 and
|Ay | = rankS ′ (y). Then
def T (x) = W (x, S ′ ) − W (y, S ′ ) + 2W (x, By ) − 2W (x, Ay )
= W (x, S) − W (x, S) + 2W (x, y) − 2W (x, w) + 2W (x, By ) − 2W (x, Ay )
≥ −def S (x) − 2|Ay | ≥ −ax .
Remark 1. The procedure MinRankInNotS correctly returns a pair (T , u), where T is a good bisection and
u is its good vertex, whenever the bisection S in input is a minimal bisection (not necessarily 3-minimal)
with a vertex in S of minimum rank.
We leverage on this property of MinRankInNotS in the next section.

3.4

There is no non-stubborn vertex of minimal rank in S

Finally, let us consider the case in which the algorithm invokes procedure MinRankInS (described as
Algorithm 3). In this case, all non-stubborn vertices of minimum rank belong to S. Moreover, all such
vertices have non-negative deficiency for otherwise the Algorithm would have stopped at Line 14.
Clearly, if MinRankInS stops at Line 5, Line 18, Line 26, Line 32, Line 39 or Line 49, then the
bisection output is good and u is a good vertex for it.
Suppose now that MinRankInS stops at Line 9, Line 30, Line 36, Line 44, Line 47 or at Line 52. Since
in all cases the algorithm returns a pair (T , v) where T is the bisection associated to a v-pair, then, by
Lemma 3, def T (v) ≥ av + 1. Thus, we only need to prove that def T (x) ≥ −ax for every non-stubborn
x ∈ T.

12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

MinRankInS():
for every vertex u ∈ S ∩ M do
for every vertex v ∈ S ∩ N (u) do
Pick a u-pair (Au , Bu ) for S with v ∈ Bu and let T be the associated bisection
if T is good then return (T , u)
if there is an obstruction y to T with def S (y) < 0 then
Let S0 = (S ∪ {y}, S \ {y})
Pick a y-pair (Ay , By ) for S0 and let T0 be the associated bisection
return (T0 , y)
if there is an obstruction y to one bisection considered at Line 4 with odd ay then
Let y be such an obstruction
else
Let y be an obstruction to one bisection considered at Line 4
Let S1 = (S ∪ {y}, S \ {y})

Let O = w ∈ S ∩ N (y) | def S (w) = ay − aw + 1
Pick a y-pair (Ay , By ) for S1 such that |Ay ∩ O| = max {|Ay |, |O|}
Let T1 be the associated bisection
if T1 is good then return (T1 , y)

if there is w ∈ S ∪ {y} \ Ay ∩ N (y) such that def S (w) = ay − aw then
Let y1 be such a vertex
else
Let y1 be an obstruction y1 to T1
Let S2 = (S2 , S 2 ) = (S ∪ {y1 } \ {y}, S ∪ {y} \ {y1 })
if there is a vertex v with rankS2 (v) < rankS2 (y) then
Pick a v-pair (Av , Bv ) for S2 and let T2 be the associated bisection
if T2 is good then return (T2 , v)
Pick an obstruction y2 to T2
Let S3 = (S 2 ∪ {y2 }, S2 \ {y2 })
Pick a y2 -pair (Ay2 , By2 ) for S3 and let T3 be the associated bisection
return (T3 , y2 )
Pick a y-pair (Ay , By ) for S2 and let T4 be the associated bisection
if T4 is good then return (T4 , y)
if there is w ∈ S ∪ {y1 } \ {y} of minimum rank for S2 with def S2 (w) < 0 then
Let S4 = (S 2 ∪ {w}, S2 \ {w})
Pick w-pair (Aw , Bw ) for S4 with y ∈ Aw and let T5 be the associated bisection
return (T5 , w)
Pick an obstruction y4 to T4
Pick a y1 -pair (Ay1 , By1 ) for S2 with y4 ∈ By1 and let T6 be the associated bisection
if T6 is good then return (T6 , y1 )
Pick an obstruction y6 to T6
if W (y6 , y) = W (y4 , y) = W (y6 , y4 ) = 1 and W (y1 , y6 ) then
Let S5 = (S 2 ∪ {y6 }, S2 \ {y6 })
Pick a y-pair (Ay , By ) for S5 and let T7 be the associated bisection
return (T7 , y)
Let S6 = (S6 , S 6 ) = (S2 ∪ {y4 } \ {y6 }, S 2 ∪ {y6 } \ {y4 })
if there is a non-stubborn vertex x in S 6 with rankS6 (x) = ℓ − 1 then
return MinRankInNotS(S6)
Pick a y1 -pair (Ay1 , By1 ) for S6 and let T8 be the associated bisection
if T8 is good then return (T8 , y1 )
Pick an obstruction y8 to T8 and let S7 = (S 6 ∪ {y8 }, S6 \ {y8 })
Pick a y8 -pair (Ay8 , By8 ) for S7 and let T9 be the associated bisection
return (T9 , y8 )
Algorithm 3: All non-stubborn vertices of minimal rank are in S

13

3.4.1

MinRankInS stops at Line 9

In this case, we have that u is a vertex of S with minimum rank ℓ. Vertex y is an obstruction of bisection
T associated with u-pair (Au , Bu ), and def S (y) < 0. By Lemma 6, y ∈ S. Observe that rankS (y) > ℓ, for
otherwise Algorithm 1 would have stopped at Line 14. From Lemma 8, we obtain that rankS0 (y) ≤ ℓ. We
remind the reader that S0 = (S ∪ {y}, S \ {y}) (see Line 7) and T0 = (S ∪ {y} \ Ay ∪ By , S \ {y} ∪ Ay \ By ).
For every non-stubborn x ∈ T0 \ {y}, we have that
def T (x) = W (x, S) − W (x, S) + 2W (x, y) − 2W (x, Ay ) + 2W (x, By ).
If x ∈ S \ Ay then
def T (x) = def S (x) + 2W (x, y) − 2W (x, Ay ) + 2W (x, By )
≥ def S (x) + 2W (x, y) − 2|Ay |
= def S (x) + 2W (x, y) − 2rankS ′ (y)
≥ def S (x) + 2W (x, y) − 2ℓ.
Since rankS (y) > ℓ, by (2), def S (y) ≤ ay − 2ℓ. By applying Lemma 2 to y ∈ S and x ∈ S we obtain that
def S (x) + 2W (x, y) ≥ −def S (y) + ay − ax ≥ −ax + 2ℓ.
Hence def T (x) ≥ −ax .
Finally, if x ∈ By , then x ∈ S and, by definition of y-pair, W (x, y) = 1. Therefore we have
def T (x) = −def S (x) + 2W (x, y) − 2W (x, Ay ) + 2W (x, By )
≥ −def S (x) − 2W (x, Ay ) + 2 ≥ −def S (x) − 2rankS ′ (y) + 2 ≥ −def S (x) − 2ℓ + 2
Since ℓ is the minimum rank, it must be the case that rankS (x) ≥ ℓ which implies that def S (x) ≤
ax + 2 − 2ℓ. Therefore, def T (x) ≥ −ax .
3.4.2

MinRankInS reaches Line 19

We remind the reader that in this case u ∈ S is a non-stubborn vertex of minimum rank ℓ and y is an
obstruction to bisection T associated with u-pair (Au , Bu ) for S. By Lemma 6, y ∈ S. Note also that
def S (y) ≥ 0, for otherwise MinRankInS
m have stopped at Line 9. From Lemma 9, it then follows
l would
a +1
that def S (y) = 0 and rankS (y) = ℓ = y2 . Moreover, given y-pair (Ay , By ) of S1 = (S ∪ {y}, S \ {y})

(see Line 16 of MinRankInS), y1 is either a vertex of S ∪ {y} \ Ay ∩ N (y) with def S (w) = ay − ay1 (see
Line 20 of MinRankInS) or it is an obstruction to bisection T1 associated with this pair (see Line 22 of
MinRankInS). Note that, by Lemma 6, even in this last case y1 ∈ S ∪ {y} \ Ay .
Properties of y and y1 . Before proving that the bisections returned by MinRankInS after Line 19 are
good, we need to establish some properties of y and y1 .
Lemma 10. W (y, y1 ) = 0.
Proof. This is obvious if y1 has been defined at Line 20 of MinRankInS.
Suppose instead that y1 is an obstruction to T1 . Then we have that def T1 (y1 ) < −ay1 . On the other
hand
def T1 (y1 ) ≥ def S1 (y1 ) − 2|By | ≥ def S1 (y1 ) − 2rankS1 (y) = def S1 (y1 ) − 2ℓ,
l
m
a +1
where we used that def S1 (y) = −def S (y) = 0 and thus rankS1 (y) = y2
= ℓ.
We then obtain that def S1 (y1 ) ≤ −ay1 + 2ℓ − 1 and

def S (y1 ) = def S1 (y1 ) − 2W (y1 , y) ≤ −ay1 − 1 + 2ℓ − 2W (y1 , y).

(6)

Suppose now, for sake of contradiction, that W (y, y1 ) = 1 and thus
def S (y1 ) ≤ −ay1 − 3 + 2ℓ.
14

(7)

At Line 4 of MinRankInS, since y1 ∈ S ∩ N (y), a y-pair (Ay , By ) for S such that y1 ∈ By has been
considered and the bisection T ′ associated with this y-pair had an obstruction that we call y ′ . It must
be the case that def S (y ′ ) ≥ 0, for otherwise the procedure would have stopped at Line 6. Then, from
′
′
Lemma 6, y ′ ∈ S and, from Lemma
l
m 9, y is a vertex of minimum rank ℓ in S and def S (y ) = 0. This
a
+1
a
+2
′
′
implies that ℓ = rankS (y ′ ) = y 2
≤ y 2 and thus ay′ ≥ 2ℓ − 2. Moreover, as we shall show next,
y1 and y ′ are neighbors. Indeed, from (7) and by applying Lemma 2 to y1 ∈ S and y ′ ∈ S, we have
2ℓ − ay1 − 3 ≥ def S (y1 ) ≥ −def S (y ′ ) − 2W (y1 , y ′ ) + ay′ − ay1
≥ 2ℓ − ay1 − 2 − 2W (y1 , y ′ ).
From the above chain of inequalities we obtain W (y1 , y ′ ) = 1. Since y ′ is an obstruction to T ′ , then
def T ′ (y ′ ) < −ay′ . On the other hand,
def T ′ (y ′ ) ≥ def S (y ′ ) − 2W (y ′ , Ay ) + 2W (y ′ , By )
≥ −2ℓ + 2W (y ′ , y1 )
≥ −(ay′ + 2) + 2 = −ay′ ,
that is a contradiction. Therefore we can conclude that y and y1 are not neighbors.
Lemma 11. If def S (y1 ) 6= ay − ay1 , then ay is even and def S (y1 ) = ay − ay1 + 1.
Proof. By applying Lemma 2 to y ∈ S and y1 ∈ S, we obtain
def S (y1 ) ≥ −def S (y) − 2W (y, y1 ) + ay − ay1 = ay − ay1 .
Since def S (y1 ) 6= ay − ay1 , it must be then the case that def S (y1 ) ≥ ay − ay1 + 1.
On the other side, by substituting W (y, y1 ) = 0 in (6), we obtain that


ay + 1
− (ay1 + 1) ≤ ay − ay1 + 1
def S (y1 ) ≤ −ay1 + 2ℓ − 1 = 2
2
, from which the claim follows.
Lemma 12. If def S (y1 ) 6= ay − ay1 , then def S (w) ≥ ay − aw + 1 − W (w, y) for every w ∈ S.
Proof. If def S (y1 ) 6= ay − ay1 , then, by Lemma 11, we have that ay is even and def S (y1 ) = ay − ay1 + 1.
We first show that def S (y1 ) = ay − ay1 + 1 implies that def S (w) ≥ ay − aw + 1 for every w ∈ S ∩ N (y).
Since y1 is an obstruction to T1 , then y1 ∈
/ Ay . By our choice of Ay (see Line 16), it must be then
the case that def S (w) = ay − aw + 1 for every w ∈ Ay .
Consider now w ∈ S \ Aw ∩ N (y). By applying Lemma 2 to y ∈ S and w ∈ S, we obtain
def S (w) ≥ −def S (y) − 2W (y, w) + ay − aw = ay − aw ,

where we used that def S (y) = 0 and w ∈ N (y). However, it cannot be the case that def S (w) = ay − aw ,
otherwise y1 was returned at Line 20, and thus def S (y1 ) = ay − ay1 , a contradiction.
Now we prove that if ay is even, then def S (w) ≥ ay − aw for every w ∈ S ∩ N (y).
We show that there is a vertex x ∈ S such that def S (x) = 0, ax = ay and W (w, x) = 0. Then, by
applying Lemma 2 to x ∈ S and w ∈ S, we obtain
def S (w) ≥ −def S (x) − 2W (x, w) + ax − aw = ay − aw .
Suppose indeed, by sake of contradiction, that w is a neighbor of every vertex x ∈ S such that
def S (x) = 0 and ax = ay . Observe that at Line 4, since w ∈ S ∩ N (y), a y-pair (Ay , By ) for S such that
w ∈ By has been considered and the bisection T ′ associated with this y-pair had an obstruction that we
call y ′ . It must be the case that def S (y ′ ) ≥ 0, for otherwise the procedure would have stopped at Line 6
of MinRankInS. Then,lfrom Lemma
6, y ′ ∈ S and, from Lemma 9, y ′ is a vertex of minimum rank ℓ in S,
m
a
+1
′
. Moreover ay′ is even, because otherwise y was returned at Line 11, that
def S (y ′ ) = 0 and ℓ = y 2
15

a

′ +2

a +2

is not possible since, by hypothesis, ay is odd. This implies that y 2 = ℓ = y2 and thus ay′ = ay .
Finally, since W (y ′ , w) = 1, then, by construction of By , W (y ′ , By ) ≥ 1.
Now, since y ′ is an obstruction to T ′ , then def T ′ (y ′ ) < −ay′ . On the other hand,
def T ′ (y ′ ) ≥ def S (y ′ ) − 2W (y ′ , Ay ) + 2W (y ′ , By )
≥ −2ℓ + 2 = −(ay′ + 2) + 2 = −ay′ ,
that is a contradiction.
Lemma 13. rankS2 (y) = rankS2 (y1 ) = ℓ.
Proof. We remind the reader that S2 = (S ∪{y1 }\{y}, S ∪{y}\{y1 }). Since, by Lemma 10, W (y, y1 ) = 0,
we have def S2 (y) = −def S (y) = 0. Hence

 

ay + 1 − def S2 (y)
ay + 1
rankS2 (y) =
=
= ℓ.
2
2
Similarly, def S2 (y1 ) = −def S (y1 ) and thus

 

ay1 + 1 − def S2 (y1 )
ay1 + 1 + def S (y1 )
rankS2 (y) =
=
.
2
2
m
l
a +1
= ℓ. If def S (y1 ) = ay − ay1 + 1 (and thus, by Lemma 11,
If def S (y1 ) = ay − ay1 , then rankS2 (y) = y2
l
m
ay +2
ay is even), then rankS2 (y) =
= ℓ.
2
Lemma 14. For every u ∈ S2 and every v ∈ S 2 \ {y}, we have

• def S2 (u) + def S2 (v) + 2W (u, v) ≥ au − av , if def S (y1 ) = ay − ay1 or u = y1 ;
• def S2 (u) + def S2 (v) + 2W (u, v) = au − av + c + 2W (y, v) + 2W (u, y1 ) − 2W (u, y) − 2W (v, y1 ), for
c ≥ max {0, 2W (u, v) − 2W (y1 , u) − W (y, v)}, otherwise.
Proof. If def S (y1 ) = ay − ay1 , then
Φ(S2 ) − Φ(S) = def S (y) + def S (y1 ) + 2W (y, y1 ) + ay1 − ay
= 0 + (ay − ay1 ) + 0 + ay1 − (ay − 1) = 0,
and thus Φ(S2 ) = Φ(S), and, since S has 3-minimal potential, then S2 has minimal potential. The
desired property then follows from Lemma 2.
Assume now that def S (y1 ) 6= ay − ay1 . Then, by Lemma 11, ay is even and def S (y1 ) = ay − ay1 + 1.
We first consider the case that u = y1 . Then,
def S2 (y1 ) + def S2 (v) + 2W (y1 , v) = −def S (y1 ) + (def S (v) − 2W (y1 , v) + 2W (y, v)) + 2W (y1 , v)
= −(ay − ay1 + 1) + def S (v) + 2W (y, v)
Since, by Lemma 12, def S (v) ≥ ay − av + 1 − W (y, v), we have
def S2 (y1 ) + def S2 (v) + 2W (y1 , v) ≥ −(ay − ay1 + 1) + (ay − av + 1 − W (y, v)) + 2W (y, v)
= ay1 − av + W (y, v) ≥ ay1 − av .
Consider now the case that u 6= y1 . Observe that def S2 (u) = def S (u) + 2W (u, y1 ) − 2W (u, y) and
def S2 (v) = def S (v) − 2W (v, y1 ) + 2W (v, y). Moreover, by applying Lemma 2 to u ∈ S and y1 ∈ S, we
have that there is cu ≥ 0 such that
def S (u) = −def S (y1 ) − 2W (y1 , u) + au − ay1 + cu = au − ay − 1 + cu − 2W (y1 , u).

16

(8)

Moreover, by Lemma 12, there is cv ≥ 0 such that def S (v) = ay − av + 1 + cv − W (y, v). By applying
Lemma 2 to u ∈ S and v ∈ S, we have that
0 ≤ def S (u) + def S (v) + 2W (u, v) + av − au
= (au − ay − 1 + cu − 2W (y1 , u)) + (ay − av + 1 + cv − W (y, v)) + 2W (u, v) + av − au
= (cu + cv ) − 2W (y1 , u) − W (y, v) + 2W (u, v).
By setting c = (cu + cv ) − 2W (y1 , u) − W (y, v) + 2W (u, v) ≥ 0, we than have
def S2 (u) + def S2 (v) + 2W (u, v)
= (def S (u) + 2W (u, y1 ) − 2W (u, y)) + (def S (v) − 2W (v, y1 ) + 2W (v, y)) + 2W (u, v)
= au − av + c + 2W (y, v) + 2W (u, y1 ) − 2W (u, y) − 2W (v, y1 ).
Lemma 15. For every u ∈ S \ {y1 } and v ∈ S \ {y}, if W (u, y) = 1 and W (u, y1 ) = 0, then def S2 (u) +
def S2 (v) + 2W (u, v) ≥ au − av − 1.
Proof. The claim follows from Lemma 14 if def S (y1 ) = ay − ay1 .
Consider instead the case that def S (y1 ) = ay − ay1 − 1. We first observe that
Φ(S2 ) − Φ(S) = def S (y) + def S (y1 ) + 2W (y, y1 ) + ay1 − ay
= 0 + (ay − ay1 + 1) + 0 + ay1 − ay = 1,
Consider now the bisection S ′ = (S2 ∪ v \ u, S 2 ∪ u \ v). It must be the case that Φ(S ′ ) ≥ Φ(S2 ) − 1,
otherwise Φ(S ′ ) < Φ(S), contradicting the minimality of S. Then,
−1 ≤ Φ(S ′ ) − Φ(S2 ) = def S2 (u) + def S2 (v) + 2W (u, v) + av − au ,
from which the claim follows.
MinRankInS stops at Line 30. Then there is a vertex v ∈ S2 , whose rank in S2 is less than rankS2 (y) =
ℓ. Note that, since def S2 (v) = def S (v) + 2W (v, y1 ) − 2W (v, y),
 


av + 1 − def S (v) − 2W (v, y1 ) + 2W (v, y)
av + 1 − def S2 (v)
=
rankS2 (v) =
2
2


av + 1 − def S (v)
=
− W (v, y1 ) + W (v, y) = rankS (v) − W (v, y1 ) + W (v, y).
2
Hence, rankS2 (v) < ℓ if and only if rankS (v) = ℓ (that is, v has minimum rank in S), W (v, y1 ) = 1 and
W (v, y) = 0. From this we obtain that for every vertex v with rankS2 (v) < ℓ, it holds that def S (v) ≥ 0
(since v has minimum rank in S and no vertex of minimum rank in S with negative deficiency can exist,
otherwise a good bisection was returned at Line 14 of Algorithm 1), and, def S2 (v) ≥ 2. We also observe
that every vertex x ∈ S 2 = S ∪ {y} \ {y1 } has rankS2 (x) ≥ ℓ. If x = y, then this follows from Lemma 13.
If x 6= y, then the claim follows since rankS x ≥ ℓ + 1, and the rank can decrease of at most one when
two vertices are swapped.
The bisection T2 associated to v-pair (Av , Bv ) for S2 has an obstruction y2 . By Lemma 6, y2 ∈ S2 \Av .
Suppose that def S2 (y2 ) ≥ 0, then, from Lemma 9, it follows that def S2 (y2 ) = 0 and has minimum rank,
i.e., rankS2 (y2 ) = ℓ − 1. However, this is a contradiction, since we showed that if rankS2 (y2 ) = ℓ − 1, then
def S2 (y2 ) ≥ 2.
It must be then the case that def S2 (y2 ) < 0 and clearly rankS2 (y2 ) ≥ ℓ (i.e., y2 has not minimum
rank in S2 ). Then, by Lemma 8, we have that rankS3 (y2 ) ≤ ℓ − 1, where S3 = (S 2 ∪ {y2 }, S2 ∪ {y2 }) (see
Line 28). Note that it must be also the case that either rankS (y2 ) ≥ ℓ + 1 or rankS (y2 ) = ℓ, W (y2 , y) = 1
and W (y2 , y1 ) = 0. Indeed rankS (y2 ) ≥ ℓ, since ℓ is the minimum rank in S. If rankS (y2 ) = ℓ, then
def S (y2 ) ≥ 0. In this case if W (y2 , y) = 0 and W (y2 , y1 ) = 1, then rankS2 (y2 ) = ℓ − 1, a contradiction.
If W (y2 , y) = W (y2 , y1 ), then def S2 (y2 ) = def S (y2 ) ≥ 0, still a contradiction.
We are now ready to prove that the bisection T3 returned at Line 30 is good. Recall that T3 is the
bisection associated to y2 -pair (Ay2 , By2 ) for S3 , i.e., T3 = (S 2 ∪ {y2 } \ Ay2 ∪ By2 , S2 \ {y2 } ∪ Ay2 \ By2 ),
where |Ay2 | = |By2 | = rankS3 (y2 ) ≤ ℓ − 1.
17

We first prove that for every x ∈ S 2 ∪ {y2 } \ Ay2 , we have that def T3 (x) ≥ −ax . If x 6= y, we
distinguish two cases. If rankS (y2 ) ≥ ℓ + 1, then by applying Lemma 2 to y2 ∈ S and x ∈ S, we have
that
def S (x) + 2W (x, y2 ) ≥ −def S (y2 ) + ay2 − ax ≥ −ax + 2ℓ,
where we used that rankS (y2 ) ≥ ℓ + 1 and thus def S (y2 ) ≤ ay2 − 2ℓ. Then,
def S2 (x) = def S (x) + 2W (x, y) − 2W (x, y1 ) ≥ −ax + 2ℓ − 2.
If rankS (y2 ) < ℓ + 1, then, as stated above, it must be the case that rankS (y) = ℓ, W (y2 , y) = 1 and
W (y2 , y1 ) = 0. Then, from Lemma 15, it holds that
def S2 (x) + 2W (x, y2 ) ≥ −def S2 (y2 ) + ay2 − ax − 1
≥ −ax + 2ℓ − 1,
where we used that rankS2 (y2 ) = rankS (y2 ) + 1 = ℓ + 1 and thus def S (y2 ) ≤ ay2 − 2ℓ.
Hence, in both cases, we have
def T3 (x) ≥ def S3 (x) − 2W (x, Ay2 ) ≥ def S2 (x) + 2W (x, y2 ) − 2(ℓ − 1)
≥ −ax + 2ℓ − 1 − 2(ℓ − 1) ≥ −ax + 1.
If x = y, then
def T3 (y) ≥ def S3 (y) − 2(ℓ − 1)
= def S2 (y) + 2W (y, y2 ) − 2(ℓ − 1)
= −def S (y) + 2W (y, y2 ) − 2(ℓ − 1),
where wel usedmthat def S2 (y) = −def S (y) because W (y, y1 ) = 0. Since, as showed above, def S (y) = 0
a +1
a +2
and ℓ = y2
≤ y2 , we have that def T3 (y) ≥ −ay + 2W (y, y2 ) ≥ −ay .

Finally, we prove that for every x ∈ By2 , def T3 (x) ≥ −ax . Recall that By2 ⊆ S2 \ {y2} and W (x, y2 ) =
1 for every x ∈ By2 . We distinguish two cases. If x 6= y1 , then
def T3 (x) ≥ −def S3 (x) − 2(ℓ − 1) = −def S2 (x) + 2W (x, y2 ) − 2(ℓ − 1)
= −def S (x) + 2W (x, y) − 2W (x, y1 ) + 2 − 2(ℓ − 1)
≥ −ax + 2ℓ − 2 + 2W (x, y) − 2W (x, y1 ) + 2 − 2(ℓ − 1) ≥ −ax ,

where we used that rankS (x) ≥ ℓ and thus def S (x) ≤ ax − 2ℓ + 2. If x = y1 , then
def T3 (y1 ) ≥ −def S3 (y1 ) − 2(ℓ − 1)
= −def S2 (y1 ) + 2W (y1 , y2 ) − 2(ℓ − 1)
= def S (y1 ) + 2 − 2(ℓ − 1),
where we used that def S2 (y1 ) = −def S (y1 ) because W (y, y1 ) = 0 and W (y1 , y2 ) = 1 because y1 ∈ By2 .
Since def S (y1 ) ≥ ay − ay1 ≥ 2(ℓ − 1) − ay1 , then def T3 (y1 ) ≥ −ay1 + 2 ≥ −ay1 .
MinRankInS stops at Line 36. In this case y and y1 have minimum rank in S2 and there is a vertex
w ∈ S \ {y} ∪ {y1 } of minimum rank ℓ and negative deficiency in S2 . Note that if rankS2 (w) ≤ rankS (w),
then def S2 (w) ≥ def S (w). Thus, since in S all vertices of minimum rank have non-negative deficiency, it
must be the case that rankS (w) = ℓ + 1, and W (w, y) = 0 and W (w, y1 ) = 1. Thus the w-pair defined
at Line 35 can be constructed.
Consider now the bisection S4 defined at Line 34. Observe that def S4 (w) = −def S2 (w) and therefore
 


aw + 1 + def S4 (w)
aw + 1 − def S4 (w)
=
rankS4 (w) =
2
2


aw + 1 − def S2 (w)
+ def S2 (w) = rankS2 (w) + def S2 (w) ≤ ℓ − 1,
=
2
18

where we used that w has rank ℓ and negative deficiency in S2 .
Now, for every x ∈ S 2 \ Aw , we have
def T5 (x) ≥ def S2 (x) + 2W (x, w) − 2rankS4 (w) ≥ −def S2 (w) + aw − ax − 2(ℓ − 1),
where we used that, by Lemma 14,
def S2 (x) + 2W (x, w) ≥ −def S2 (w) + aw − ax + 2W (y, x) + 2W (w, y1 ) − 2W (w, y) − 2W (x, y1 )
≥ −def S2 (w) + aw − ax .
Since rankS2 (w) = ℓ, then def S2 (w) ≤ aw − 2ℓ + 2, from which we achieve that def T5 (x) ≥ −ax .
Finally, let us consider x ∈ Bw ⊆ S2 . We have
def T5 (x) ≥ −def S2 (x) − 2rankS4 (w) ≥ −def S2 (x) − 2(ℓ − 1).
However, by hypothesis w has minimum rank among the non-stubborn vertices and thus it must be the
case that rankS2 (x) ≥ rankS2 (w) = ℓ which implies that def S2 (x) ≤ ax −2ℓ+2. Therefore, def T (x) ≥ −ax .
3.4.3

MinRankInS reaches Line 40

In this case y and y1 have minimum rank in S2 , but there is an obstruction y4 to bisection T4 associated
with y-pair (Ay , By ) for S2 . From Lemma 6, y4 ∈ S 2 . Then, from Lemma 14, it holds that
def S2 (y1 ) + def S2 (y4 ) + 2W (y1 , y4 ) ≥ ay1 − ay4 .
Thus, by Lemma 7, y4 and y1 are adjacent. This shows that it is always possible to pick a y1 -pair
(Ay1 , By1 ) as defined at Line 38. However, there is obstruction y6 to the bisection T6 associated with
this pair.
We start by proving some properties of y4 and y6 and of the bisection S6 defined in Line 45 and
obtained by swapping y4 and y6 . In particular, we will prove that S6 is a minimal bisection. Note that
this implies that, according to Remark 1, if the bisection is returned at Line 47, then it enjoys the desired
properties. Hence, it will be sufficient to show that the bisections returned at Line 44 and Line 52 are
good.
Properties of y4 and y6 .
Lemma 16. Φ(S6 ) = Φ(S2 ) − 1 = Φ(S). Hence, since S is 3-minimal, S6 is minimal.
Proof. We first remind the reader that
Φ(S2 ) − Φ(S) = def S (y) + def S (y1 ) + 2W (y, y1 ) + ay1 − ay
≥ 0 + (ay − ay1 + 1) + 0 + ay1 − (ay − 1) = 1,
and thus Φ(S2 ) ≥ Φ(S) + 1. Moreover, since S is 3-minimal, Φ(S6 ) ≥ Φ(S).
Suppose now, by sake of contradiction, that Φ(S2 ) − 1 6= Φ(S) or Φ(S6 ) 6= Φ(S2 ). In both cases we
have that Φ(S6 ) ≥ Φ(S2 ) and thus
0 ≤ Φ(S6 ) − Φ(S2 ) = def S2 (y6 ) + def S2 (y4 ) + 2W (y6 , y4 ) + ay4 − ay6 .
It is then possible to apply Lemma 7 to y6 and y4 , and have that these two vertices are adjacent. Thus,
since by construction y4 ∈ By1 , W (y6 , By1 ) ≥ 1. Moreover, by Lemma 7, rankS2 (y6 ) = ℓ and thus
minimal. Hence, it must be the case that def S2 (y6 ) ≥ 0 (otherwise the algorithm stops at Line 36) and
def S (y6 ) ≤ ay6 − 2ℓ + 2, from which we achieve that ay6 − 2ℓ + 2 ≥ 0 and then def S (y6 ) ≥ −(ay6 − 2ℓ + 2).
Therefore,
def T6 (y6 ) = def S2 (y6 ) − 2W (y6 , Ay1 ) + 2W (y6 , By1 ) ≥ −(ay6 − 2ℓ + 2) − 2ℓ + 2 = −ay6 ,
that is a contradiction because def T6 (y6 ) < −ay6 since y6 is an obstruction to T6 .

19

By Lemma 14, since Φ(S6 ) = Φ(S2 ) − 1, it must be the case that def S (y1 ) 6= ay − ay1 . Then, from
a +2
Lemma 11, we have that ay is even (hence, ℓ = y2 ) and def S (y1 ) = ay − ay1 + 1.
Lemma 17. One of the following conditions is satisfied:
1. W (y6 , y) = W (y4 , y) = W (y6 , y4 ) = 1 and W (y1 , y6 ) = 0;
2. W (y6 , y) = 1 and W (y4 , y) = 0;
3. W (y6 , y1 ) = W (y6 , y4 ) = 0.
Proof. By Lemma 16 and Lemma 14, we have that
−1 = Φ(S6 ) − Φ(S2 ) = def S2 (y6 ) + def S2 (y4 ) + 2W (y6 , y4 ) + ay4 − ay6
= c + 2W (y, y4 ) + 2W (y6 , y1 ) − 2W (y6 , y) − 2W (y4 , y1 )

(9)

= c + 2W (y, y4 ) + 2W (y6 , y1 ) − 2W (y6 , y) − 2
for c ≥ max {0, 2W (y6 , y4 ) − 2W (y1 , y6 ) − W (y, y4 )}.
Suppose, for sake of contradiction, that conditions 1-3 are not satisfied. First consider the case that
W (y, y4 ) = 0. Then, W (y6 , y) = 0. Now, if W (y6 , y1 ) = 1, then (9) fails. If W (y6 , y1 ) = 0. Then,
W (y6 , y4 ) = 1. Therefore, c ≥ 2 and thus (9) fails.
Consider now that W (y4 , y) = 1. Then, either W (y6 , y) = 0 or W (y6 , y4 ) = 0 or W (y6 , y) =
W (y6 , y4 ) = W (y1 , y6 ) = 1. In the first case and in the third case, (9) fails. In the second case, we must
have W (y6 , y1 ) = 1, and then (9) fails again.
Lemma 18. cx ≤ 1 + 2W (y1 , x) for every x ∈ S.
Proof. If cx ≥ 2 + 2W (y1 , x), then
def S (x) = ax − ay − 1 + cy6 − 2W (y1 , y6 ) ≥ ay6 − ay + 1.
Therefore,

where we used that ℓ =

 l m
ay
ay6 + 1 − def S (y6 )
=
= ℓ − 1,
rankS (y6 ) =
2
2

ay +2
2 .



Anyway, this is a contradiction since ℓ is the minimum rank in S.

Lemma 19. If W (y6 , y) = 1 and W (y4 , y) = 0, then there is a vertex in S 6 of minimum rank.
Proof. Note indeed that
def S6 (y) = def S2 (y) + 2W (y6 , y) − 2W (y4 , y) = 2,
where we used the hypothesis and the fact that def S2 (y) = 0 since W (y, y1 ) = 0.
Hence,

 

ay + 1 − def S6 (y)
ay + 1
rankS6 (y) =
=
− 1 = ℓ − 1.
2
2

The claim then follows, by observing that for every x ∈ S2 , x 6= y6 , rankS2 (x) ≥ ℓ (otherwise a
bisection would be returned at Line 30), and thus rankS6 (x) ≥ ℓ − 1.
Moreover for x = y4 , by Lemma 12, we have
def S2 (y4 ) = def S (y4 ) − 2W (y1 , y4 ) + 2W (y, y4 )
≥ ay − ay4 + 1 + W (y, y4 ) − 2W (y1 , y4 )
Hence,
def S6 (y4 ) = −def S2 (y4 ) − 2W (y4 , y6 )
≤ ay 4 − ay + 1
= ay4 − 2ℓ + 3.
Then rankS6 (y4 ) ≥ ℓ − 1.
20

≥ ay − ay4 − 1.

MinRankInS stops at Line 44. In this case we have that W (y6 , y) = W (y4 , y) = W (y6 , y4 ) = 1 and
W (y1 , y6 ). Let S5 be the bisection defined at Line 42 of MinRankInS, i.e., S5 = (S 2 ∪ {y6 }, S2 \ {y6 }).
Observe that def S5 (y) = def S2 (y) + 2W (y, y6 ) = −def S (y) − 2W (y, y1 ) + 2W (y, y6 ) = 2, where we used
that def S (y) = 0, W (y, y1 ) = 0 from Lemma 10, and W (y, y6 ) = 1. Hence,

 

ay + 1 − def S7 (y)
ay + 1
rankS5 (y) =
=
− 1 = ℓ − 1,
2
2
a +2

where we used that ℓ = y2 .
We now prove that the bisection T7 = (S 2 ∪ {y6 } \ Ay ∪ By , S2 \ {y6 } ∪ Ay \ By ) defined at Line 43
is good, that is, for every non-stubborn vertex in x ∈ S 2 ∪ {y6 } \ Ay ∪ By it holds that def T7 (x) ≥ ax .
Consider first x ∈ S 2 \ Ay = S \ {y1 } ∪ {y} \ Ay . Observe that
def S5 (x) = def S2 (x) + 2W (x, y6 )
= def S (x) + 2W (x, y) − 2W (x, y1 ) + 2W (x, y6 ).
Since, from Lemma 12, def S (x) ≥ ay − ax + 1 − W (x, y), we have that
def S5 (x) ≥ ay − ax + 1 + W (x, y) − 2W (x, y1 ) + 2W (x, y6 )
≥ 2ℓ − ax − 1 + W (x, y) − 2W (x, y1 ) + 2W (x, y6 ),
where we used that ℓ =

ay +2
2

and thus ay ≥ 2ℓ − 2. Therefore,

def T7 (x) ≥ def S5 (x) − 2rankS5 (y)
≥ 2ℓ − ax − 1 + W (x, y) − 2W (x, y1 ) + 2W (x, y6 ) − 2ℓ + 2
= −ax + 1 + W (x, y) − 2W (x, y1 ) + 2W (x, y6 )
We next show that either W (x, y1 ) = 0 or W (x, y) + W (x, y6 ) ≥ 1, from which it follows that def T7 (x) ≥
−ax + 1.
Suppose by sake of contradiction that W (x, y1 ) = 1 and W (x, y) + W (x, y6 ) = 0. Then def S2 (x) =
ay − ax + 1 + W (x, y) − 2W (x, y1 ) = ay − ax − 1. On the other side, from (8) we have
def S2 (y6 ) = ay6 − ay − 1 + cy6 − 2W (y6 , y) = ay6 − ay − 3 + cy6 .
′

Let S = (S2 \ {y6 } ∪ {x}, S 2 \ {x} ∪ {y6 }). Since S is 2-minimal and, by Lemma 16, Φ(S2 ) = Φ(S) + 1,
we need that
−1 ≤ Φ(S ′ ) − Φ(S2 ) = def S2 (y6 ) + def S2 (x) + 2W (y6 , x) − ay6 + ax = cy6 − 4.
However, this is a contradiction since, by Lemma 18, cy6 ≤ 1 + 2W (y1 , y6 ) = 1, where we used that
W (y1 , y6 ) = 0 by hypothesis.
Consider now x = y6 . Observe that, from 8 and W (y1 , y6 ) = 0, it follows that
def S5 (y6 ) = −def S2 (y6 ) = −def S (y6 ) + 2W (y6 , y) − 2W (y6 , y1 )
= −ay6 + ay + 3 − cy6
= −ay6 + 2ℓ + 1 − cy6 ,
where we used that ℓ =

ay +2
2 .

Since, by Lemma 18, cy6 ≤ 1 + 2W (y1 , y6 ) = 1, we have

def T7 (y6 ) = def S5 (y6 ) − 2(ℓ − 1) = −ay6 + 3 − cy6 ≥ −ay6 + 2.
Finally, consider x ∈ By . Recall that in this case W (x, y) = 1. From (8), we achieve
def S5 (x) = def S2 (x) − 2W (x, y6 )
= def S (x) − 2 + 2W (x, y1 ) − 2W (x, y6 )
= ax − ay − 3 + cx − 2W (x, y6 )
= ax − 2ℓ − 1 + cx − 2W (x, y6 ).
Then, by Lemma 18
def T7 (x) = −def S5 (y6 ) − 2(ℓ − 1) = −ax + 3 − cx + 2W (x, y6 ) ≥ −ax ,
where we used that cx ≤ 1 + 2W (x, y1 ) ≤ 3.
21

MinRankInS stops at Line 52. We first note that if MinRankInS reaches Line 44, then it must be
the case that W (y6 , y1 ) = W (y6 , y4 ) = 0. Indeed, it cannot be the case that W (y6 , y) = W (y4 , y) =
W (y6 , y4 ) = 1, otherwise a bisection would be returned at Line 44. And, it cannot be the case that
W (y6 , y) = 1 and W (y4 , y) = 0, otherwise, according to Lemma 19, there is a vertex of minimum rank
in S 6 , and thus a bisection would be returned at Line 47. Then, by Lemma 17, we have W (y6 , y1 ) =
W (y6 , y4 ) = 0.
Consider then S6 as defined at Line 45, i.e., S6 = (S6 , S 6 ) = (S2 ∪ {y4 } \ {y6 }, S 2 ∪ {y6 } \ {y4 }). First
note that
def S6 (y1 ) = def S2 (y1 ) + 2W (y1 , y4 ) − 2W (y1 , y6 ) = def S2 (y1 ) + 2,
where W (y1 , y4 ) = 1, as follows from Lemma 7 when applied to y4 and y1 in S2 . Consequently
rankS6 (y1 ) = rankS2 (y1 ) − 1 = ℓ − 1.
Moreover observe that every vertex x ∈ S6 \ {y1 } of minimum rank in S6 has positive deficiency.
Indeed, either x ∈ S2 \ {y1 , y6 } or x = y4 . In the first case, rankS2 (x) ≥ ℓ (otherwise a bisection
was returned at Line 30). Thus, rankS6 (x) = ℓ − 1 if and only if rankS2 (x) = ℓ, W (x, y4 ) = 1 and
W (x, y6 ) = 0. However, if rankS2 (x) = ℓ, then def S2 (x) ≥ 0 (otherwise a bisection was returned at
Line 36). Then def S6 (x) = def S2 (x) + 2W (x, y4 ) − W (x, y6 ) ≥ 2.
If instead x = y4 , then, by Lemma 12, there is cy4 ≥ 0 such that
def S2 (y4 ) = def S (y4 ) − 2W (y1 , y4 ) + 2W (y, y4 )
= ay − ay4 + 1 + W (y, y4 ) − 2W (y1 , y4 ) + cy4 .
Hence,
def S6 (y4 ) = −def S2 (y4 ) − 2W (y4 , y6 )
= ay4 − ay − 1 − W (y, y4 ) + 2W (y1 , y4 ) − cy4 .
Then rankS6 (y4 ) = ℓ − 1 if an only if W (y, y4 ) = cy4 = 0 and W (y1 , y4 ) = 1. In this case, def S6 (y4 ) =
ay4 − ay + 1 = −def S (y4 ). The claim then follows by showing that def S (y4 ) < 0. Indeed, if def S (y4 ) ≥ 0,
then ay4 ≤ ay + 1. Then, since ay is even,

 
 

ay4 + 1 − def S (y4 )
ay 4 + 1
ay + 2
rankS (y4 ) =
≤
≤
= ℓ.
2
2
2
Hence, y4 has minimum rank in S, that is a contradiction.
Finally, note that every vertex in S 6 has rank at least ℓ, otherwise a bisection was returned at Line 47.
Consider now the bisection T8 defined at Line 48. Recall that T8 is the bisection associated with
an y1 -pair (Ay1 , By1 ) for S6 . Since T8 has not been returned at Line 49, then it has an obstruction y8 .
By Lemma 6, y8 ∈ S6 \ Ay1 . If def S6 (y8 ) ≥ 0, then, from Lemma 9, it follows that def S6 (y8 ) = 0 and
has minimum rank. However, this is a contradiction, since we showed that rankS6 (y2 ) = ℓ − 1 implies
def S6 (y2 ) > 0.
It must be then the case that def S6 (y8 ) < 0 and clearly rankS6 (y8 ) ≥ ℓ (i.e., y8 has not minimum
rank in S6 ). Then, by Lemma 8, we have that rankS7 (y8 ) ≤ ℓ − 1, where S7 = (S 6 ∪ {y8 }, S \ {y8 }) has
been defined at Line 50.
We are now ready to prove that the bisection T9 returned at Line 52 is good. Recall that T9 is the
bisection associated to y8 -pair (Ay8 , By8 ) for S7 , i.e., T9 = (S 6 ∪ {y8 } \ Ay8 ∪ By8 , S6 \ {y6 } ∪ Ay6 \ By6 ),
where |Ay8 | = |By8 | = rankS7 (y8 ) ≤ ℓ − 1.
We first prove that for every x ∈ S 6 ∪ {y8 } \ Ay8 , we have that def T9 (x) ≥ −ax . If x 6= y6 , then, since
by Lemma 16, S6 is minimal, by applying Lemma 2 to y8 ∈ S6 and x ∈ S 6 , we have that
def S7 (x) = def S6 (x) + 2W (x, y8 )
≥ −def S6 (y8 ) + ay8 − ax
≥ −ax + 2ℓ − 2,
where we used that rankS6 (y8 ) ≥ ℓ and thus def S6 (y8 ) ≤ ay8 − 2ℓ + 2. Therefore,
def T9 (x) ≥ def S7 (x) − 2W (x, Ay8 )
≥ −ax + 2ℓ − 2 − 2(ℓ − 1) = −ax .
22

If x = y6 , then, recalling that W (y6 , y4 ) = 0 and thus def S6 (y6 ) = −def S2 (y6 ), we have
def T9 (y6 ) ≥ def S7 (y6 ) − 2(ℓ − 1)
= def S6 (y6 ) + 2W (y6 , y8 ) − 2(ℓ − 1)
= −def S2 (y6 ) + 2W (y6 , y8 ) − 2(ℓ − 1).
By (8) and by recalling that W (y6 , y1 ) = 0,
def S2 (y6 ) = def S (y6 ) + 2W (y6 , y1 ) − 2W (y6 , y)
≥ ay6 − ay − 1 − 2W (y6 , y)
= ay6 − 2ℓ + 1 − 2W (y6 , y),
where we used that ℓ =

ay +2
2 .

Hence,

def T9 (y6 ) = −ay6 + 2ℓ − 1 + 2W (y6 , y) + 2W (y6 , y8 ) − 2(ℓ − 1)
≥ −ay6 + 1.
Finally, we prove that for every x ∈ By8 , def T9 (x) ≥ −ax . Recall that By8 ⊆ S6 \ {y, 6, y8 } and
6 y4 , then
W (x, y8 ) = 1 for every x ∈ By8 . We distinguish two cases. If x =
def T9 (x) ≥ −def S7 (x) − 2(ℓ − 1) = −(def S6 (x) − 2W (x, y8 )) − 2(ℓ − 1)
= −(def S2 (x) + 2W (x, y6 ) − 2W (x, y4 ) − 2W (x, y8 )) − 2(ℓ − 1)
≥ −ax + 2ℓ − 2 − 2W (x, y6 ) + 2W (x, y4 ) + 2 − 2(ℓ − 1) ≥ −ax ,
where we used that rankS (x) ≥ ℓ and thus def S2 (x) ≤ ax − 2ℓ + 2.
If x = y4 , then
def T9 (y4 ) ≥ −def S7 (y4 ) − 2(ℓ − 1)
= −(def S6 (y4 ) − 2W (y4 , y8 )) − 2(ℓ − 1)
= −(−def S2 (y4 ) − 2W (y4 , y8 )) − 2(ℓ − 1)
= def S2 (y4 ) + 2 − 2(ℓ − 1),
where we used that def S6 (y4 ) = −def S6 (y4 ) because W (y6 , y4 ) = 0 and W (y4 , y8 ) = 1 because y4 ∈ By8 .
By Lemma 12, we have that
def S2 (y4 ) = def S (y4 ) + 2W (y4 , y) − 2W (y4 , y1 )
≥ ay − ay4 + 1 + W (y, y4 ) − 2W (y4 , y1 )
= 2ℓ − ay4 − 1 + W (y, y4 ) − 2W (y4 , y1 )
Then,
def T9 (y4 ) ≥ 2ℓ − ay4 − 1 + W (y, y4 ) − 2W (y4 , y1 ) + 2 − 2(ℓ − 1)
≥ −ay4 + 3 + W (y, y4 ) − 2W (y4 , y1 )
≥ −ay4 + 1.

4

Lower Bound

We next show that deciding if it is possible to subvert the majority when starting from a weaker minority
is a computationally hard problem, even if we start with a minority of size very close to n−1
2 . The main
result of this section is given by the following theorem.
Theorem 2. For every constant 0 < ε < 133
155 , given a graph G with n vertices, it is NP-hard to decide
whether there exists a subvertable belief assignment with at most n−1
2 (1−ε) vertices in the initial minority.

23

Proof. To prove our result, we will use a reduction from the NP-hard problem 2P2N-3SAT, that is, the
problem of deciding whether a 3SAT formula in which every variable appears as positive in two clauses
and as negative in two clauses has a truthful assignment or not (the NP-hardness of 2P2N-3SAT follows
by the results in [8]).
Given an instance of 2P2N-3SAT, i.e. a Boolean formula φ with C clauses and V variables where
3C = 4V (thus, C is a multiple of 4), we will construct a graph G(φ) with odd n vertices, such that φ
has a satisfying assignment if and only if there exists a belief assignment b for the vertices of G(φ), with
at most n−1
2 (1 − ε) vertices having belief 1, and a sequence of updates leading from b to an equilibrium
in which at least n+1
2 vertices adopt opinion 1.
The graph G(φ) contains the following vertices and edges.
• For each variable x of φ, G(φ) includes a variable gadget for x consisting of 25 vertices and 50
edges (see Figure 1).
The vertices of the variable gadget for x are: the literal vertices, x and x; vertices v1 (x), . . . , v7 (x),
v1 (x), . . . , v7 (x), and w1 (x), . . . , w7 (x); vertex v0 (x) and w0 (x).
The edges of the variable gadget for x are: edges (x, vi (x)), (x, vi (x)) and (w0 (x), wi (x)), for
i = 1, . . . , 7; edges (vi (x), vi+1 (x)) and (vi (x), vi+1 (x)) for i = 1, . . . , 6; edges (v0 (x), v7 (x)),
(v0 (x), v7 (x)), (v0 (x), w0 (x)), (w0 (x), vi (x)), (w0 (x), vi (x)).
w1 (x)

w2 (x)

w3 (x)

w4 (x)

w5 (x)

w6 (x)

w7 (x)

w0 (x)

v1 (x) v2 (x) v3 (x) v4 (x) v5 (x) v6 (x) v7 (x) v0 (x) v7 (x) v6 (x) v5 (x) v4 (x) v3 (x) v2 (x) v1 (x)

x

x

Figure 1: The variable gadget.
• For each clause c of φ, graph G(φ) includes a clause gadget for c consisting of 18 vertices and 32
edges (see Figure 2).
The vertices of the clause gadget for c are: the clause vertex c; vertices u1 (c), u2 (c); vertices
υ1 (c), . . . , υ15 (c).
The 32 edges of the clause gadget are; edges (c, u1 (x)), (c, u2 (x)); edges (ui (c), υj (c)) with i = 1, 2
and j = 1, . . . , 15.
c

u1 (c)

u2 (c)

υ1 (c)

υ15 (c)
υ2 (c)

υ3 (c)

υ13 (c)

υ14 (c)

Figure 2: The clause gadget.
• For every clause c in φ, G(φ) contains edges between the clause vertex c and the three literal vertices
corresponding to the literals appearing c. Thus, each literal vertex x is connected to exactly two
clause vertices, corresponding to the two clauses in which that literal appears in φ.
24

• Graph G(φ) contains a clique disconnected from the rest of the graph of size N + 6C + 1 vertices,
with even N such that 2 ≤ N ≤ 133−147ε
C. (Note that our choice of ε implies that 133−147ε
C ≥ 2.)
4ε
4ε
• N+

123C
4

additional isolated vertices.


+ 1 (recall that C is a multiple
Observe that the total number of vertices in G(φ) is n = 2 N + 147C
4
is
an
integer).
of 4, so 147C
4
The stubbornness level of the vertices of G(φ) is defined as follows. All vertices belonging to gadgets
and the isolated vertices have stubbornness level less than 1/2. Vertices in the clique are divided in two
+6C
groups. N clique vertices have a stubbornness level greater than NN+6C+1
. We will call them asocial
vertices, since they never have an incentive to declare an opinion different from their own belief, whatever
are the opinions declared by the remaining vertices in the clique. Call the remaining clique vertices
−6C+2(i−1)
−6C+2i
< αci < NN−6C+2i+1
c0 , . . . , c6C ; then vertex ci has a stubbornness level αci such that NN−6C+2(i−1)+1
(since N is even, then the denominator is never 0 and it always has the same sign of the numerator, from
which he have that αci ≥ 0, as desired). This implies that vertex ci adopts an opinion different from her
own belief if and only if at least N + i clique vertices adopt that opinion.
A belief assignment to the vertices of G(φ) is called proper if it assigns belief 1 to the following
vertices:
• for every variable x, vertex w0 (x) and only one of the two literal vertices in the gadget of x;
• for every clause c, vertices u1 (c) and u2 (c) in the gadget of c;
• the N asocial clique vertices.
• All the remaining vertices have belief 0.
n−1
Hence, in a proper profile the number of vertices with belief 1 is 2V + 2C + N = 7C
2 + N ≤ 2 (1 − ε),
133−147ε
C).
(remind that N ≤
4ε
To prove Theorem 2 we will use the following two lemmas. The first lemma proves that there exists
a proper subvertable belief assignment for G(φ) if and only φ is satisfiable.

Lemma 20. The Boolean formula φ is satisfiable if and only if there exists a proper belief assignment
to the vertices of G(φ) that is subvertable.
Proof. We observe that in a proper belief assignment all clique vertices eventually adopt opinion 1, even
if their belief is 0. In fact, consider vertices ci , for i = 0, . . . , 6C in this sequence: when vertex ci is
selected there are N + i vertices in the clique with opinion 1 and then ci has an incentive to adopt
opinion 1.
Let b be a proper belief assignment. Using an argument similar to what shown in [1], we can prove
that: (i) there exists a sequence of updates that leads from b to an equilibrium in which 17 vertices of
every variable gadget have opinion 1 but no sequence of updates can reach an equilibrium from b where
more than 17 vertices in a variable gadget have opinion 1; (ii) there exists a sequence of updates that
leads to an equilibrium in which 17 vertices of the clause gadget have opinion 1; (iii) the updates lead
to an additional number of C clause vertices adopting opinion 1 in the equilibrium if and only if φ is
satisfiable.
Thus, we have that if φ is satisfiable then there exists a sequence of updates leading to an equilibrium
n+1
where N + 6C + 1 + 17V + 17C + C = N + 147C
4 + 1 = 2 vertices have opinion 1. Otherwise, if φ is not
satisfiable, any sequence of updates leads to an equilibrium where less than n/2 vertices have opinion
1.
To conclude our proof we will show that we can ignore non-proper assignments since there is no
sequence of updates that leads from a non-proper belief assignment to an equilibrium where the majority
of vertices adopt opinion 1.
Lemma 21. For each non-proper belief assignment b to the vertices of G(φ) that assigns opinion 1 to
at most 7C
2 + N vertices, there is no sequence of updates that leads from b to an equilibrium where at
least n+1
2 vertices adopt opinion 1.

25

Proof. We start observing that if the number of clique and isolated vertices in G(φ) adopting opinion 1
is strictly less than N , then no clique vertex with opinion 0 will never adopt opinion 1 (the same trivially
holds for isolated vertices). Thus, in this case, even if it would be possible to convince all vertices in the
variable and clause gadgets to adopt opinion 1, the number of vertices with opinion 1 in the equilibrium
n−1
would be at most 25V + 18C + N − 1 = N + 147C
4 −1 < 2 .
Let us now focus on a belief assignment that assigns belief 1 to at most 7C/2 = 2C + 2V vertices
from variable and clause gadgets. By adopting an argument similar to what given in [1], we can then
prove that, if this belief assignment is such that a sequence of updates leads to an equilibrium where at
least n+1
2 vertices adopt opinion 1, then this belief assignment must be proper.

References
[1] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Persiano.
Minority becomes majority in social networks. In Proceedings of the 11th International Conference
on Web and Internet Economics (WINE), pages 74–88, 2015.
[2] David Bindel, Jon M. Kleinberg, and Sigal Oren. How bad is forming your own opinion? In
Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 55–66, 2011.
[3] Flavio Chierichetti, Jon M. Kleinberg, and Sigal Oren. On discrete preferences and coordination. In
Proceedings of the 14th ACM Conference on Electronic Commerce (EC), pages 233–250, 2013.
[4] Morris H. DeGroot. Reaching a consensus.
69(345):118–121, 1974.

Journal of the American Statistical Association,

[5] Diodato Ferraioli, Paul W. Goldberg, and Carmine Ventre. Decentralized dynamics for finite opinion
games. In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT),
pages 144–155, 2012.
[6] Noah E. Friedkin and Eugene C. Johnsen. Social influence and opinions. Journal of Mathematical
Sociology, 15(3–4):193–205, 1990.
[7] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve.
SIAM Journal on Computing, 20(1):56–87, February 1991.
[8] Ryo Yoshinaka. Higher-order matching in the linear lambda calculus in the absence of constants
is NP-complete. In Jürgen Giesl, editor, Term Rewriting and Applications, volume 3467 of Lecture
Notes in Computer Science, pages 235–249. Springer Berlin Heidelberg, 2005.

26

