We further extend this problem to that of multigraphs, defining Simple b**-Edge Cover of Multigraphs as**
follows.

Name: Simple b**-Edge Cover of Multigraphs**
Instance: An undirected multigraph G = (V, E**), a function** b : V → Z
+ **and positive integer** q.

Question: Does there exist a subset of at most q edges C ⊆ E such that each vertex v ∈ V **is incident to**
at least b(v**) edges in** C?

This variation is also polynomial-time computable, as follows.

Theorem 1 Simple b**-Edge Cover for Multigraphs is polynomial-time computable.**
Proof: We demonstrate how to compute Simple b-Edge Cover of Multigraphs using Capacitated b**-Edge**
Cover, which we define as follows.

Name: Capacitated b-Edge Cover **(See also [18, chapter 34])**
Instance: An undirected graph G = (V, E**), a function** b : V → Z
+**, a capacity function** c : E → Z
+**, and**
positive integer q.

Question: Does there exist a multisubset of edges C ⊆ E such that each vertex v ∈ V **is incident to at**
least b(v) edges in C and such that each e ∈ E is chosen by C **with frequency at most** c(e)?
Let G = (**V, E**), b : V → Z
+, and q > 0 be an instance of Simple b**-Edge Cover of Multigraphs.**
We construct an instance of Capacitated b-Edge Cover as follows. Let G′ be a complete graph of V **. For**
each pair v1, v2 ∈ V , we set the capacity c(v1, v2) to the number of edges between v1 and v2 in G.

Simple b-Edge Cover of Multigraphs, and several variations thereof, is of **interest in solving some election**
manipulation problems in which the voters always distinguish exactly two candidates from the remaining candidates. More specifically, in such a construction, the vertices **correspond to candidates and the edges** to the voters, who distinguish two candidates from the remaining. We introduce two additional versions of Simple b**-Edge Cover of Multigraphs, which will be of interest to problems involving weights and prices for**
voters.

Name: Simple Weighted b**-Edge Cover of Multigraphs**
Instance: An undirected multigraph G = (V, E**), a function** b : V → Z
+**, weight function** w : E → Z
+ and positive integer q.

Question: Does there exist a subset of edges C ⊆ E of total weight at most q **such that each vertex** v ∈ V
is incident to at least b(v**) edges in** C?
Name: Simple b**-Edge Weighted Cover of Multigraphs**