Initially, p has ||E|| **vetoes, while each of** p
′, b**, and** b
′ have at least ||E|| vetoes. Each v ∈ V **has exactly**
||E|| + b(v**) vetoes.**
Consider a weighted b-edge cover of G of weight at most q**. It is possible to bribe the voters corresponding**
to this b-edge cover, at cost at most q, to veto {b, b′} **instead. On the other hand, consider a bribery of cost**
at most q which makes p a winner. Clearly, only the voters corresponding to the edges in E **can be bribed,**
as all of the other voters have price q + 1. It must be the case that for each v ∈ V , at least b(v**) voters are** bribed. This corresponds to a b**-edge cover.**
This shows that $bribery of 2-veto elections is at least as hard as Simple Weight b**-Edge Cover of Multigraphs. However, the complexity of this problem remains an open problem.**
In the next result, we find two problems of control that are equivalent to another variation of b**-Edge**
Cover we defined as Simple b**-Edge Weighted Cover of Multigraphs. In this problem, each edge counts**
differently toward the multiplicity of the vertex being covered. Edges are, however, unweighted, in that a typical instance will seek a covering by some number, q**, of edges.**
Theorem 26 Control by adding weighted voters in 2**-veto elections, and by deleting weighted voters in** 2approval elections, is polynomial-time equivalent to Simple b**-Edge Weighted Cover of Multigraphs.**
Proof: **Consider the case of weighted 2-veto control by adding voters.**
Consider an election E = (C, V ). For each candidate c ∈ C, define Score(c**) to be the current score of**
candidate c in E. Without loss of generality, we add only voters that do not veto p. To ensure p**'s victory, for** each candidate c 6= p currently beating p, we must add vetoes of weight totaling at least Score(c)− **Score(**p).

We construct a graph of vertex set C − {p}. For each voter v of weight w(v) vetoing candidates {**a, b**},
we add an edge of multiplicity w(v) connecting vertices a and b. For each candidate c ∈ C − {p}**, we assign** the b-value of its corresponding vertex b(c) = max(Score(c) − Score(p), 0).

Observe that in a valid covering of at most q vertices, adding these q **voters ensures that each candidate**
c 6= p receives vetoes of total weight at least max(Score(c) − Score(p), 0), and thus p beats c**. Conversely,**
in any addition of voters, without loss of generality, we may disregard any additional voters whom veto p. Since each candidate c 6= p must receive vetoes of total weight at least max(Score(c) − Score(p), **0) to ensure** p's victory, edges corresponding to the additional voters must correspond to a b**-Edge cover.**
Conversely, consider an instance of Simple b-Edge Weighted Cover of Multigraphs. Let G = (V, E**) be a**
multigraph. For each v ∈ V , let b(v) denote the minimum multiplicity of edges that v **is to be covered, and** for each edge e ∈ E, let w(e**) denote the multiplicity of the edge** e.

Let M = maxvb(v) denote the largest b**-value of the vertices. Construct an election over the candidates**
{p} ∪ V such that initially p receives M vetoes, and each v ∈ V receives M − b(v**) vetoes. For each**
e = (v1, v2) ∈ E, let there be one unestablished voter of weight w(e) vetoing {v1, v2}.

Consider an addition of at most q voters that elects p. As p **cannot gain any vetoes from the addition**
of the voters, clearly, each v ∈ V must gain at least b(v) vetoes. This corresponds to a b**-Edge Cover of at** most q edges. Conversely, adding at most q edges corresponding to a b-Edge Cover adds at least b(v**) vetoes** to each v ∈ V , giving each v ∈ V at least M **vetoes, and electing** p.