Dominik Kaaser
email: dominik@cosy.sbg.ac.at

Frederik Mallmann-Trenn

Emanuele Natale
email: natale@di.uniroma1.it

On the Voting Time of the Deterministic Majority Process *

Keywords: 1998 ACM Subject Classification F, 2, 2 Nonnumerical Algorithms and Problems Keywords and phrases distributed voting, majority rule Digital Object Identifier 10, 4230/LIPIcs, MFCS, 2016, 55 1

In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, each node adopts the majority opinion among its neighbors. It is known that this process always converges in O (|E|) rounds to a two-periodic state in which every node either keeps its opinion or changes it in every round.

) that the O (|E|) bound on the convergence time of the deterministic binary majority process is even for dense graphs tight. However, in many graphs such as the complete graph the process converges in just a constant number of rounds from any initial opinion assignment.

We show that it is NP-hard to decide whether there exists an initial opinion assignment for which it takes more than k rounds to converge to the two-periodic state, for a given integer k. We then give a new upper bound on the voting time of the deterministic binary majority process. Our bound can be computed in linear time by carefully exploiting the structure of the potential function by Goles and Olivos. We identify certain modules of a graph G to obtain a new graph G ∆ . This new graph G ∆ has the property that the worst-case convergence time of G ∆ is an upper bound on that of G. Our new bounds asymptotically improve the best known bounds for various graph classes.

Introduction

Distributed voting is a fundamental problem in distributed computing. We are given a network of players modeled as a graph. Each player in the network starts with one initial opinion out of a set of possible opinions. Then the voting process runs either synchronously in discrete rounds or asynchronously according to some activation mechanism. During these rounds in the synchronous case, or upon activation in the asynchronous case, the players are allowed to communicate with their direct neighbors in the network with the main goal to eventually agree on one of the initial opinions. If all nodes agree on one opinion, we say this opinion wins and the process converges. Usually, voting algorithms are required to be simple, fault-tolerant, and easy to implement [START_REF] Hassin | Distributed Probabilistic Polling and Applications to Proportionate Agreement[END_REF][START_REF] Johnson | Design & Analysis of Fault Tolerant Digital Systems[END_REF].

In this paper, we study the deterministic binary majority process which is defined as follows. We are given a graph G = (V, E) where each node has one out of two opinions. The process runs synchronously in discrete rounds where each node in every round computes and adopts the majority opinion among all of its neighbors. It is known that this process always converges to a two-periodic state. The convergence time of a given graph for a given initial opinion assignment is the time required until this two-periodic state is reached. In this work we improve the bounds on the convergence time for given initial opinions and then we analyze the voting time of the process, which is the maximum convergence time over all possible initial opinion assignments.

In distributed computing, various variants of the majority process are used in faulttolerant distributed consensus algorithms. In the analysis of structures of large networks, the deterministic binary majority process has widespread applications in the study of socalled influence networks [START_REF] Frischknecht | Convergence in (Social) Influence Networks[END_REF]. Early applications can be found in distributed databases [START_REF] Gifford | Weighted Voting for Replicated Data[END_REF]. Further fields include sensor networks [START_REF] Bénézit | Interval consensus: From quantized gossip to voting[END_REF], the analysis of opinions in social networks [START_REF] Mossel | Opinion Exchange Dynamics[END_REF], social behavior in game theory [START_REF] Deng | On the Complexity of Cooperative Solution Concepts[END_REF], chemical reaction networks [START_REF] Doty | Timing in Chemical Reaction Networks[END_REF], neural and automata networks [START_REF] Goles | Neural and Automata Networks[END_REF], and cells' behavior in biology [START_REF] Cardelli | The Cell Cycle Switch Computes Approximate Majority[END_REF]. Variants of the deterministic binary majority process have been used in the area of distributed community detection [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF][START_REF] Kothapalli | On the Analysis of a Label Propagation Algorithm for Community Detection[END_REF][START_REF] Cordasco | Community Detection via Semi-Synchronous Label Propagation Algorithms[END_REF]. In this context, the proposed community detection protocols exhibit a convergence time which can be bounded by the voting time of the deterministic binary majority process.

Among its many probabilistic variants that have been previously considered, plenty of work concerns randomized voting where in each step every node is allowed to contact a random sample of its neighbors and updates its current opinion according to the majority opinion in that sample [START_REF] Aldous | Reversible Markov Chains and Random Walks on Graphs[END_REF][START_REF] Brahma | Fair Leader Election by Randomized Voting[END_REF][START_REF] Cooper | Coalescing Random Walks and Voting on Connected Graphs[END_REF][START_REF] Donnelly | Finite particle systems and infection models[END_REF][START_REF] Hassin | Distributed Probabilistic Polling and Applications to Proportionate Agreement[END_REF][START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF][START_REF] Lanchier | Voter model and biased voter model in heterogeneous environments[END_REF][START_REF] Liggett | Interacting Particle Systems[END_REF][START_REF] Mallmann-Trenn | Bounds on the voting time in terms of the conductance[END_REF][START_REF] Oliveira | On the coalescence time of reversible random walks[END_REF].

In an algorithmic game theoretic setting, the deterministic binary majority process can be seen as the simplest discrete preference games [START_REF] Chierichetti | On Discrete Preferences and Coordination[END_REF]. In this game theoretic perspective, the existence of monopolies has been investigated [START_REF] Auletta | Minority Becomes Majority in Social Networks[END_REF]. A monopoly in a graph is a set of nodes which start with the same opinion and cause all other nodes to eventually adopt this opinion. In the distributed computing area, a lot of research has been done to find small monopolies, see for example [START_REF] Peleg | Local majorities, coalitions and monopolies in graphs: a review[END_REF]. It has also been shown that there exist families of graphs with constant-size monopolies [START_REF] Berger | Dynamic Monopolies of Constant Size[END_REF]. More recently, classes of graphs which do not have small monopolies have been investigated [START_REF] Peleg | Immunity against Local Influence[END_REF].

Many of these results relate to the voting time of the deterministic binary majority process. It was proven independently by Goles and Olivos [START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF], and Poljak and Sůra [START_REF] Poljak | On periodical behaviour in societies with symmetric influences[END_REF] with the same potential function argument that the deterministic binary majority process always converges to a two-periodic state. They later (independently) refined and generalized the potential function argument in several directions [START_REF] Goles | Local Graph Transformations Driven by Lyapunov Functionals[END_REF][START_REF] Goles | Decreasing Energy Functions and Lengths of Transients for Some Cellular Automata[END_REF][START_REF] Goles-Chacc | Decreasing energy functions as a tool for studying threshold networks[END_REF][START_REF] Poljak | On an application of convexity to discrete systems[END_REF]. Their proof was popularized in the Puzzled columns of Communications of the ACM [START_REF] Winkler | Puzzled: Delightful Graph Theory[END_REF][START_REF] Winkler | Puzzled: Solutions and Sources[END_REF]. Recently, the same problem has been studied on infinite graphs w.r.t. a given probability distribution on the initial opinion assignments [START_REF] Benjamini | Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs[END_REF]. In [START_REF] Tamuz | Majority Dynamics and the Retention of Information[END_REF], the authors provide a bound on the number of times a node in a given bounded-degree graph changes its opinion. Both [START_REF] Benjamini | Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs[END_REF] and [START_REF] Tamuz | Majority Dynamics and the Retention of Information[END_REF] also investigate the probability that in the two-periodic state all nodes hold the same opinion.

As for the maximum time it takes for the process to converge over all initial opinion assignments, Frischknecht et al. [START_REF] Frischknecht | Convergence in (Social) Influence Networks[END_REF] note that the potential argument by Goles et al. [START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF][START_REF] Poljak | On periodical behaviour in societies with symmetric influences[END_REF][START_REF] Winkler | Puzzled: Solutions and Sources[END_REF] can be used to prove an O (|E|) upper bound. They furthermore show that this upper bound is tight in general, by designing a class of graphs in which the deterministic binary majority process takes at least Ω |V | 2 rounds to converge from a given initial opinion assignment. This construction has later been extended to prove lower bounds for weighted and multi-edges graphs by Keller et al. [START_REF] Keller | How Even Tiny Influence Can Have a Big Impact![END_REF].

Once the process converges to the two-periodic state, each node stays either with its own opinion or changes its opinion in every round. A lot of attention has been given to the opinions to which the deterministic binary majority process converges. However, regarding the voting time, besides the O (|E|) upper bound that follows from the result by Goles et al. [START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF][START_REF] Poljak | On periodical behaviour in societies with symmetric influences[END_REF][START_REF] Winkler | Puzzled: Solutions and Sources[END_REF], no further upper bound on the voting time that holds for any initial opinion assignment has been proved. Still, one can observe that in many graphs the voting time is much smaller than O (|E|). For example, the voting time of the complete graph is one.

We show that for the deterministic binary majority process the question whether the voting time is greater than a given number is NP-hard. While for many generalizations of the deterministic binary majority process many decision problems are known to be NP-hard, at the best of our knowledge this is the first NP-hardness proof that does not require any additional mechanisms besides the bare majority rule of the deterministic binary majority process. However, as we show in the rest of the paper, it is possible to obtain upper bounds on the voting time which can be computed in linear time. A module of a graph is a subset of vertices S such that for each pair of nodes u, v ∈ S it holds that N (u) \ S = N (v) \ S, where N (u) denotes the set of neighbors of a node u. By carefully exploiting the structure of the potential function by Goles et al. we leverage the particular behavior that certain modules, which we call families, exhibit and prove that the voting time of a graph can be bounded by the voting time of a smaller graph that can be constructed in linear time by contracting suitable vertices.

We obtain a new upper bound that asymptotically improves the previous O (|E|) bound on graph classes which are characterized by a high number of modules that are either cliques or independent sets. An example for such graphs is the Turán graph T (n, r), formed by partitioning a set of n vertices into r subsets of (almost) equal sizes and connecting two vertices by an edge whenever they belong to different subsets. For the convergence time of the Turán graph T (n, r) we obtain an O r 2 bound, compared to the previously best known bound of O n 2 . Also, for the convergence time of full d-ary trees we get an O (|V |/d) bound, compared to O (|V |) originating from the O (|E|) bounds. Further examples include the clique and the star graph, for which our bound gives a constant O (1) convergence time. Our bound relies on a well-known graph contraction technique based on identifying equivalent nodes. This technique is used in other related disciplines as well, including parallel and distributed computing. See, for example, the notion of identical nodes in the work by Sarıyüce et al. [START_REF] Sarıyüce | Shattering and Compressing Networks for Betweenness Centrality[END_REF].

Preliminaries

We are given a graph G = (V, E) and an initial opinion assignment defined as follows.

Definition 1. An opinion assignment f t in round t ≥ 0 is a function f t : V → {0, 1} which assigns for each v ∈ V one out of two possible opinions. We will also denote opinion 1 as white and opinion 0 as black. The opinion assignment at time t = 0 is called initial opinion assignment.

The deterministic binary majority process can be defined as follows. Let v be an arbitrary but fixed vertex and N (v) the set of neighbors of v. To compute f t+1 (v) the node v computes the majority opinion of all of its neighbors in N (v). In the case of a tie the node behaves lazily, that is, v stays with its own opinion. Otherwise, there is a clear majority and the node adopts the majority opinion. This leads to the following definition.

M F C S 2 0 1 6

55:4

On the Voting Time of the Deterministic Majority Process Definition 2. Let G = (V, E) be a graph and let f 0 be an initial opinion assignment such that f 0 : V → {0, 1}. The deterministic binary majority process is the series of opinion assignments that satisfy the rule

f t+1 (v) =        0 if |{u ∈ N (v) : f t (u) = 0}| > |{u ∈ N (v) : f t (u) = 1}| 1 if |{u ∈ N (v) : f t (u) = 0}| < |{u ∈ N (v) : f t (u) = 1}| f t (v) otherwise.
Note that the pair (G, f 0 ) completely determines the behavior of the system according to the majority process. We now define the main object of this work, the voting time.

Definition 3. Given a graph G = (V, E) and any initial opinion assignment f 0 on V , the convergence time T of the majority process on G w.r.t.

f 0 is T = T(G, f 0 ) = min {t : ∀v f t+2 (v) = f t (v)} . The voting time of G is defined as max f0∈{0,1} V T(G, f 0 ).
Observe that T is indeed the number of steps until the process converges to a twoperiodic state. This holds since the process is completely determined by the current opinion assignment. Thus

f t+2 (v) = f t (v) also implies that f t+3 (v) = f t+1 (v) for all nodes v.
In the following we assume without loss of generality that G is connected. For disconnected graphs the deterministic binary majority process runs independently in each connected component. Therefore, the resulting upper bounds on the voting time can be replaced by the maximum over the corresponding bounds in the individual connected components of G.

Our Contribution

First we define the voting time decision problem vtdp and show that it is NP-complete.

Definition 4 (voting time decision problem vtdp).

For a given graph G and an integer k, is there an assignment of initial opinions such that the voting time of G is at least k? Theorem 5. Given a general simple graph G, vtdp is NP-complete.

In Section 3 we extend known approaches to derive upper bounds on the voting time, which are tight for general graphs. In Section 3.2, we identify the following subsets of nodes that play a crucial role in determining the voting time of the deterministic binary majority process.

Definition 6. A set of nodes S is called a family if and only if for all pairs of nodes

u, v ∈ S we have N (u) \ {v} = N (v) \ {u}. We say that a family S is proper if |S| > 1.
The set of families of a graph forms a partition of the nodes into equivalence classes. Our main contribution is a proof that the voting time of the deterministic binary majority process is bounded by that of a new graph obtained by contracting its families into one or two nodes, as stated in the following theorem.

Definition 7. Given a graph G = (V, E), its asymmetric graph G ∆ = (V ∆ , E ∆ ) is the subgraph of G induced by the subset V ∆ ⊆ V constructed
by contracting every family of odd-degree non-adjacent nodes to one node, and any other proper family to two nodes.

Let in the following V even be the set of even-degree vertices in V and, analogously, let V odd be the set of odd-degree vertices. Based on above definition of G ∆ , we give the following bound on the voting time.

Theorem 8. Given any initial opinion assignment on a graph G = (V, E), the voting time of the deterministic binary majority process is at most

1 + min |E ∆ | - |V ∆ odd | 2 , |E ∆ | 2 + |V ∆ even | 4 + 7 4 • |V ∆ | .
Furthermore, this bound can be computed in O (|E|) time.

As mentioned before, this bound becomes O r 2 for the Turán graph T (n, r) and O (|V |/d) for d-ary trees. Finally, in Section 3 we also give some insight into further interesting computational properties of the deterministic binary majority process. For example, we disprove a monotonicity of the convergence time w.r.t. the potential function and argue that the voting time is not, at least straightforwardly, bounded by the diameter of the graph.

NP-Completeness

If it was possible to efficiently compute the worst-case voting time, there would have been not much interest in investigating good upper bounds for it. In this section, we show that this is unlikely to be the case. We prove Theorem 5 by reducing 3sat to the voting time decision problem. Given Φ ∈ 3sat, we construct a graph G = G(Φ) such that the deterministic binary majority process on G simulates the evaluation of Φ. The graph G consists of h layers where h = 3 + 4 • n. The first layer represents an assignment of the variables in Φ, the remaining layers represent Φ and ensure that the assignment of variables in Φ is valid. We will show that if Φ is satisfiable, then there exists an initial assignment of opinions for which the convergence time is exactly h + 1. If, however, Φ is not satisfiable, then any assignment of opinions will result in a convergence time strictly less than h + 1. We now give the formal proof.

Let Φ ∈ 3sat be a Boolean formula in 3-conjunctive normal form. Let n be the number of variables of Φ. Let m be the number of clauses of Φ. The Boolean formula is of the form

Φ = (l 1,1 ∨ l 1,2 ∨ l 1,3 ) ∧ • • • ∧ (l m,1 ∨ l m,2 ∨ l m,3 ), where l i,j ∈ {x 1 , x 1 , x 2 , x 2 , • • • , x n , x n } is a literal for 1 ≤ i ≤ m and 1 ≤ j ≤ 3.
We construct a graph G to simulate the evaluation of Φ as follows. Let = 10 • (m + n) + 1. The graph consists of several layers. On the first layer, we place so-called literal cliques of size , and on the layers above we place the gates. In our reduction, we use or-gates, an and-gate, and 2/3-gates. Each gate consists of one or several nodes. Additionally, we have two so-called mega-cliques K white and K black of size .

Let g be an arbitrary but fixed gate. We denote a node on a layer below g which does not belong to g but is connected to g as input node to g. Additionally, we will denote a node that belongs to g and is connected to another gate on a layer above g as output node of g.

In the following, we assume that opinion 1, white, corresponds to Boolean true and 0, black, corresponds to false. The main idea of the construction is to show that an activation signal is transmitted from the bottom up through all layers. If the current assignment of opinions on the literal cliques corresponds to a satisfying assignment of Boolean values to Φ, then the process requires h + 1 steps. The main purpose of the or-gates and the and-gate is to evaluate Φ. The 2/3-gates check whether the opinion assignment to literal nodes is valid. That is, we need to enforce that the corresponding literal nodes for x i and x i are of opposite colors for every variable x i of Φ. If either this condition is violated and variables x i exist for which x i = x i or the current assignment of opinions on the literal cliques does not corresponds to a satisfying assignment of Boolean values to Φ, the construction enforces that the process stops prematurely after strictly fewer than h + 1 steps.

M F C S 2 0 1 6

55:6

On the Voting Time of the Deterministic Majority Process Layer 1: Literal Cliques. We represent each variable x i with two cliques, one for x i and one for x i . Each clique has a size of which is defined above. Note that is odd. Additionally, we distinguish three so-called representative nodes in each of these cliques. Furthermore, we add two cliques of size to the graph which we call mega-cliques. Intuitively, these mega-cliques represent the Boolean values true and false. We will show that they cannot have the same color in order to achieve a long convergence time. The mega-cliques are used in all other gates.

( x 1 ∨ x 2 ∨ x 3 ) K x 1 x 1 K x 2 x 2 K x 1 x 1 K x 1 x 1 K x 2 x 2 K x 1 x 1 K white or layer 2 layer 1
Layer 2: Parallel or-Gates. The or-gates are placed on layer 2 and consist of one node v which is also the output node. There is one or-gate for every clause. Fix a clause (l j,1 ∨ l j,2 ∨ l j,3 ). Input nodes are three pairs of nodes (v 1 , v 1 ), (v 2 , v 2 ), and (v 3 , v 3 ), where (v 1 , v 1 ) are two representative nodes of the literal clique for l j,1 , (v 2 , v 2 ) are representatives of l j,2 , and (v 3 , v 3 ) are representatives of l j,3 . That is, for each literal in the clause we connect the or-gate on layer 2 to two of the three representative nodes of the corresponding literal clique on layer 1. The output node v is additionally connected to 4 nodes of the K white mega-clique. Intuitively, we use the or-gates to verify that for each clause at least one literal is true. All clauses are evaluated simultaneously using an or-gate for each clause. The or-gate is shown in Figure 1.

Layer 3: and-Gate. There is exactly one and-gate on layer 3. This and-gate consists of one output node denoted u 0 , which has the following input nodes. It is connected to every output node of the or-gates on layer 2 and to m -2 distinct nodes of the K black mega-clique.

Intuitively, the and-gate is used toverify that every clause is satisfied. It is shown in Figure 2.

Layers 4 to 3 + 4n: 2/3-Gates. The 2/3-gates consist of a path v 1 , v 2 , v 3 , and v 4 . Each node of this path is connected to two distinct nodes of the K white . The output node of the gate is v 4 . The node v 1 of the first 2/3-gate on layer 4 is connected to the and-gate on layer 3. The node v 1 of each of the following 2/3-gates is connected to the node v 4 of the previous 2/3-gate. Additionally, the input node of the i-th 2/3-gate is connected to three distinct nodes of the literal clique representing x i and to three distinct nodes of the literal clique representing x i on layer 1. The output node of the final 2/3-gate is connected to K black . An example is shown in Figure 3. The 2/3-gates are used to verify that we do not have variables x i in Φ for which the literal cliques of x i and x i have the same color. Observe that 2/3-gates span over 4 layers, and we have n such 2/3-gates. Literal cliques, or-gates, and the and-gate use only one layer, and 2/3-gates span over 4 layers. Therefore, the total number of layers is h = 3 + 4 • n, which results from one layer for the literal cliques, one layer for the or-gates, one layer for the and-gate, and 4 • n layers containing n concatenated 2/3-gates. A detailed example for such a graph G is given in [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF]. Based on above description of G we prove the following lemmas, which are then used to show Theorem 5.

v 4 v 3 v 2 v 1 2 /3 K white K xi K xi layer 1 layers 4 to 3 + 4 • n

Lemma 9. If Φ is satisfiable, then there exists an assignment of opinions such that the convergence time in G is at least h + 1.

To show Theorem 9, we construct an initial opinion assignment for which the gates change from black to white one layer after the other, assuming Φ is satisfiable. The full proof can be found in [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF].

It remains to show that if Φ is not satisfiable, then the voting time in G is strictly less than h + 1. Recall that the voting time is the maximum of the convergence time over all possible initial opinion assignments. Lemma 10. If Φ is not satisfiable, then there is no assignment of opinions such that the convergence time in G is at least h + 1.

Before we prove this lemma, we several auxiliary lemmas which require the following definitions. Let u 0 denote the output node of the and-gate. Consider the graph G induced by the nodes of the and-gate and the nodes of the 2/3-gates. Let u i be the node at distance i to u 0 in G . We observe that G is a path u 0 , . . . , u κ consisting of the 4 • n + 1 top layers of the graph G. Consequently, κ = 4 • n and u i is the i-th node on this path.

Definition 11 (Stable Time).

We define the stable time s(v) for any node v ∈ V to be the first time step such that v does not change its opinion in any subsequent time step t > s(v) over all possible initial configurations. That is,

s(v) = min t : ∀f 0 ∈ {0, 1} V ∀t ≥ t f t (v) = f t (v) .
Accordingly, let for any subset V ⊆ V be s(V ) defined as s(V ) = max {s(v) : v ∈ V }.

In the following, let V K be the set of nodes of all cliques in G(Φ), that is, the nodes contained in the literal cliques and in the mega-cliques on layer 1. Furthermore, let V K r be the set of representatives of the cliques and V K -= V K \ V K r . That is, every clique K on layer 1 consists of K -∪ K r . Finally, let V or be the set of all output nodes of or-gates. The following lemma shows that the layers become stable one after the other.

M F C S 2 0 1 6

55:8

On the Voting Time of the Deterministic Majority Process Lemma 12. It takes at most 3 time steps for the layers 1 and 2 consisting of literal cliques and or-gates to become stable. Precisely, we have (i) s (V K -) = 1, (ii) s (V K r ) = 2, and (iii) s (V or ) = 3.

The above lemma gives bounds on the stable time of layers 1 and 2. In the following, we argue that whenever a node changes its opinion in any step t after time step 3, it will not change its color in any subsequent time step t ≥ t any more. We therefore define the so-called activation time of a node v ∈ G as follows.

Definition 13 (Activation Time). Let c be the color of the K black mega-clique at time 2 and let f 0 be an arbitrary but fixed initial opinion assignment. We define the activation time of a node v ∈ G to be the first time step after time step 3 in which the node v adopts opinion c. That is, a(v) = min {t ≥ 3 : f t (v) = c}. If v does not change its color after time step 3 we write a(v) = 3.

We now use the above definition to state the following lemma, which describes that every node u i ∈ G with i ≥ 1 changes its color at most once after time step 3. Note that this covers the nodes of the 2/3-gates. Lemma 14. Let f 0 be an arbitrary but fixed initial opinion assignment. Let t be the activation time w.r.t. f 0 of the node

u i ∈ G with i ≥ 1 such that t = a(u i ). Then for all t ≥ t we have f t (u i ) = f t (u i ).
Proof. By Theorem 12, all nodes u ∈ V K r are stable at t ≥ 2. We now distinguish two cases.

Case 1: i mod 4 = 1. Observe that u i can only change its color at time t = a(u i ), if it had a different color than K white in the previous round. This holds, since every node u i with i mod 4 = 1 has the same number of connections to K white than to nodes in V \ K white . Since furthermore the process behaves lazy, any node u i which has the same color as K white cannot change its opinion back to the opposite color any more. Case 2: i mod 4 = 1. The node u i is a v 1 node of the j-th 2/3-gate with j = i/4 . Therefore it is connected to three representatives of each literal clique for x j and x j . The literal representatives of x j and x j are stable at time t ≥ 2. Now if x j and x j have the same color c, then u i has 6 > |N (u i )|/2 edges to nodes of color c. Therefore, the node does not change its color any more after time step 3. That is, we have a(u i ) = 3 and also f t (u i ) = c for any consecutive time step t ≥ 3. If, however, x j and x j do not have the same color, these edge cancel each other out and the color of node u i is determined by u i-1 , u i+1 , and K white . Therefore, the same argument as in the first case holds.

In the following we examine the behavior of layer 3 which contains only the and-gate. Recall that u 0 is the output node of the and-gate. The next lemma describes the following fact. The and-gate u 0 can only change its color in a time step t ≥ 4 if u 1 changed its color in time step t -1. After this change at time t, the node u 0 cannot change its color again. Lemma 15. Let f 0 be an arbitrary but fixed initial opinion assignment and let furthermore t be the round after node u 1 has been activated such that t = a(u 1 ) + 1. For all consecutive rounds t ≥ t we have f t (u 0 ) = f t (u 0 ). That is, the and-gate does not change its opinion any more once the node u 1 has become stable.

The following lemma implies that in order to reach a convergence time of h + 1 the gates on the path u 0 , . . . , u κ in G have to activate one after the other starting with u 0 at time 4. Recall that κ = 4 • n.

Lemma 16. Let f 0 be an arbitrary but fixed initial opinion assignment and let u

i ∈ G be a node with 0 ≤ i ≤ κ. If a(u i ) < i + 4 w.r.t. f 0 , then T (G(Φ), f 0 ) < h + 1.
In the following two lemmas, we enforce that initial opinion assignments which do not represent valid assignments of Boolean values to literal cliques result in premature termination of the deterministic binary majority process in G(Φ). An assignment is called illegal if there exist literal cliques such that the majority of x i and the majority of x i have the same initial color.

Lemma 17. For any illegal initial opinion assignment

f I to G(Φ), the convergence time T (G(Φ), f I ) is strictly less than h + 1.
Lemma 18. If after two time steps K white and K black have the same color, the process stops after strictly fewer steps than h + 1.

From above lemmas we conclude that Theorem 10 holds, and together with Theorem 9, Theorem 10 yields Theorem 5. The full proofs can be found in [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF].

Proof of Theorem 5. It is easy to see that vtdp is in NP. Furthermore, we can polynomially reduce 3sat to vtdp. The correctness proof of the reduction follows from Theorem 9 and Theorem 10. Therefore we conclude that vtdp is NP-complete.

Bounds on the Voting Time

Since the problem is NP hard, we cannot hope to calculate the voting time of a graph efficiently. Nevertheless, in this section we show, that it is possible to obtain non-trivial upper bounds on the voting time that are easy to compute. This section is dedicated to proving our upper bound on the voting time, Theorem 8. The main contribution of this theorem is the influence of symmetry which is studied in Section 3.2. We start by giving a formal version of the potential function argument [START_REF] Goles | Periodic behaviour of generalized threshold functions[END_REF][START_REF] Poljak | On periodical behaviour in societies with symmetric influences[END_REF] as conceived in [START_REF] Winkler | Puzzled: Solutions and Sources[END_REF]. In the following we assume that each edge in {x, y} ∈ E can be replaced by two directed edges (x, y) and (y, x). The main idea is based on so-called bad arrows defined as follows.

Definition 19. Let G = (V, E) be a graph with initial opinion assignment f 0 . Let v denote an arbitrary but fixed node and u ∈ N (v) a neighbor of v. Let t denote an arbitrary but fixed round. The directed edge (v, u) is called bad arrow if and only if the opinion of u in round t + 1 differs from the opinion of v in round t. We will also denote the bad arrows which have their tail at round t = 0 as initial bad arrows.

Intuitively, each of these directed edges (v, u) can be seen as advice given from v to u in the voting process. In the case of a bad arrow the advice was not followed by u since it has a different opinion in the following round than v. Observe that each bad arrow is incident at exactly two nodes and thus we say it is outgoing in the node at its tail and incoming in the node at its head. An example of such a bad arrow can be seen in Figure 4. The idea of the proof is to define a potential function φ t that is strictly monotonically decreasing over the time. Let f 0 be any initial opinion assignment. The potential function φ t is simply the number of bad arrows defined in Theorem 19, that is

φ t = φ t (G, f t ) = |{(v, u) ∈ E : f t+1 (u) = f t (v)}| .
For the full proof, see [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF]. Note that in Theorem 20 it is assumed that all nodes of the graph have odd-degree. In the following we show how to remove this assumption. Definition 21. Let G = (V, E) be a graph. The graph G * = (V, E * ) is the graph obtained by adding a self loop to every node of even degree in G. More formally, The proof is based on the fact that for every node v ∈ V the sequence of opinions, (f t (v)), is exactly the same for the deterministic binary majority process in G as for the deterministic binary majority process in G * . For the full proof, see [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF].

E * = E ∪ v∈Veven (v, v) .
Observe, that while the number of bad arrows is used in the potential function, the convergence time is, however, not monotone w.r.t. the number of initial bad arrows.

Lemma 23. The convergence time is not monotone w.r.t. the number of initial bad arrows.

The upper bound on the voting time considered in [START_REF] Keller | How Even Tiny Influence Can Have a Big Impact![END_REF] follows from the 2 • |E| upper bound on the number of bad arrows of Theorem 20. Clearly, this result can be improved by a factor of 2 by simply applying the observation that the number of initial bad arrows in G * is at most |E| -|V odd |/2. Therefore, from Theorem 22 we obtain the following corollary.

Corollary 24. The voting time of the deterministic binary majority process on any graph

G = (V, E) is at most 1 + |E| -|V odd |/2.
Remark. Theorem 24 is tight for general graphs up to an additive constant of 1. Indeed, consider a path with an initial opinion assignment on which the opinions alternate except for the last two nodes, which share the same opinion.

Suppose that, instead of specifying the initial opinion assignment, we decide in advance what bad arrows are there. We can do that by deciding for each ordered pair (u, v) for which {u, v} ∈ E whether we want to have a bad arrow going from u to v. We formalize this notion by means of the following definitions. In proving upper bounds on the voting time we consider the bad arrows assignment determined by the initial opinion assignment. One may wonder whether in doing so we are losing information. In the following lemma we show that, given a valid bad arrows assignment, we can reconstruct the initial opinion assignment up to exchanging black and white (and up to two more possibilities in bipartite graphs).

Lemma 26.

Let G be a connected graph and let β be a valid bad arrows assignment on G. If the graph is not bipartite, there are exactly two opinion assignments, otherwise there are exactly four opinion assignments that determine β.

Proof. Let v ∈ V denote an arbitrary but fixed vertex. We now denote the set {v} as N 0 and the set of direct neighbors of v as N 1 to define the i-th neighborhood N i for i ≥ 2 as

N i =   u∈Ni-1 N (u)   \   i-1 j=1 N j   .
We now show by an induction on k = 0, 1, 2, . . . that the colors of all nodes in N 2•k are determined by the color of v. The base-case is trivial since for k = 0 we have N 0 = {v}. For the induction step we observe that according to the induction hypothesis the color of each node in N 2•k is determined. We now observe that the color at time 1 of each node in N 2•k+1 is determined by β and the colors at time 0 of the nodes in N 2•k . Vice versa, also the colors at time 0 of nodes in N 2•(k+1) are determined by β and the colors at time 1 of each node in N 2•k+1 . This concludes the induction.

An example is shown in Figure 5. In this figure it is clear that v and, e.g., u 1 must have a different color, for the following reason. Since u 1 does not have a bad arrow to its neighbor in N 1 , it has the same color in the next round as this neighbor. But this neighbor's color in the next round is different to the current color of v because of the bad arrow assignment.

Observe that from above induction the lemma follows immediately for bipartite graphs. We can fix the colors for two arbitrary nodes, one from each of the two sets of non-adjacent nodes, to determine all other nodes' colors. This gives us four possible opinion assignments M F C S 2 0 1 6

55:12

On the Voting Time of the Deterministic Majority Process for a given bad arrow assignment β. If the graph is not bipartite there must exist a cycle of odd length. The opinion assignments for all nodes of this cycle are determined by β with the same argument as in above induction. Therefore, not only the colors of even neighborhoods N 2k are determined, but also of odd neighborhoods N 2k+1 . This leaves us with exactly two possible initial opinion assignments, which concludes the proof.

Improved Bounds for Dense Graphs

We observe that Theorem 24 is (almost) tight, and it gives us a voting time linear in the number of vertices for sparse graphs where |E| = O (|V |). However, for dense graphs with, e.g., |E| = Ω |V | 2 there is room for improvement. Now the main goal in this following subsection is to reduce the dominant term of the voting time even further, which leads us to the following theorem which is formally shown in [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF].

Theorem 27. Let G = (V, E) be a graph. For any initial opinion assignment f 0 on G, the convergence time of the deterministic binary majority process is at most

1+ |E| 2 + |Veven| 4 + 7 4 •|V |.
Remark. One might intuitively assume that the voting time is bounded by the diameter of the network. However, this is not true, at least straightforwardly, as there exist graphs G where the convergence time w.r.t. a given initial opinion assignments f 0 is asymptotically larger than the diameter of the network, that is, T(G, f 0 ) diam(G).

The Influence of Symmetry

We observe that the majority process is much faster on graphs that exhibit certain types of symmetry, such as the star graph, the complete graph and many other graphs in which several nodes share a common neighborhood. We investigate this feature of the process to further improve the bounds obtained so far. We recall that a set of nodes S is called a family if and only if for all nodes u, v ∈ S we have N (u) \ {v} = N (v) \ {u}. The key fact is that these nodes of any family will behave in a similar way after the first step.

Definition 28. Let fam (u) denote the family of u. We write u ∼ v if fam (u) = fam (v).

Lemma 29. The relation ∼ defines an equivalence class. In particular, all nodes in the same family either form a clique or a stable set, and they all have the same degree in G.

Corollary 30. For any graph G, its asymmetric graph G ∆ is well-defined.

Proof. According to Theorem 29, the set of families is a partition of the nodes of G. By construction of G ∆ , every family S in G is replaced by one or two nodes in G ∆ . Therefore, there is a bijection between the families in G and the corresponding node or pair of nodes in G ∆ . Hence G ∆ is well-defined.

We are now ready to prove Theorem 8.

Remark. While we show that for the voting time we have max f T(G ∆ , f ) ≥ max f T(G, f ), in general it is not the case that T(G ∆ , f ) ≥ T(G, f ) for every opinion assignment f . A formal statement along with a counterexample is given in [START_REF] Kaaser | On the Voting Time of the Deterministic Majority Process[END_REF].

Proof of Theorem 8. Let v and v be two nodes of the same family fam (v) = fam (v ), having the same color at time t. Since v and v observe the same opinions in their respective neighborhood, v and v will also have the same color anytime after t. It follows that if at some time t there is a bad arrow going from v to some neighbor u (or from u to v), then D. Kaaser, F. Mallmann-Trenn, and E. Natale 55:13 there will also be a bad arrow from v to u (or from u to v ). In particular, this implies that whenever the number of bad arrows adjacent to v is decreased by some amount c, also the identical number of bad arrows adjacent to v will be decrease by the same amount c.

Recall the proofs of Theorem 24 and Theorem 27. An estimate of the voting time is obtained by upper bounding the number of bad arrows that can possibly disappear during the process. The main argument is the following. It suffices to only consider the bad-arrows adjacent to v in G ∆ , since the corresponding bad arrows adjacent to v will disappear whenever those adjacent to v do.

Let v and v be two nodes with fam (v) = fam (v ) having a different color at time t. We can divide every such family that contains nodes of different opinions into two sets S 0 and S 1 according to their initial opinion in the first round. Note that all nodes in either set behave identically. In particular, an adjacent bad arrow from a node u to all nodes of either set disappears at the same time. Since there is bijection between the families of G and the pairs of nodes and singletons of G ∆ , and by applying Theorem 24 and Theorem 27 we can bound the voting time by bounding the bad arrows in G ∆ . This yields the first part of the claim. Using [START_REF] Cournier | A New Linear Algorithm for Modular Decomposition[END_REF], one can obtain the modular decomposition of G in O (|E|) time steps. In another O (|E|) time steps one can select from the modular decomposition those modules that form a family, using that all nodes of a family have the same degree. Hence, G ∆ can be constructed in linear time.

Figure 1

 1 Figure 1 Literal nodes and or-gate.

Figure 2

 2 Figure 2 and-gate.

Figure 3

 3 Figure 3 The 2/3-gate.

Theorem 20 . 1 Figure 4 A

 2014 Figure 4 A bad arrow from node v to node u in round t.

FromTheorem 22 .

 22 the definition it follows that |E * | = |E| + |V even |. The voting time of the deterministic binary majority process on any graph G = (V, E) is at most 1 + W bad , where W bad is an upper bound on the number of initial bad arrows in G * .

1 Figure 5

 15 Figure 5The opinions of each second neighborhood are uniquely determined.

Acknowledgement. We would like to thank our supervisors Petra Berenbrink, Andrea Clementi, Robert Elsässer, and Claire Mathieu for helpful discussions and important hints.

Research was supported by Austrian Science Fund (FWF): P 27613