  Electoral control types are ways of trying to change the outcome of elections
by altering aspects of their composition and structure [BTT92]. We say two
compatible (i.e., having the same input types) control types that are about the
same election system E form a collapsing pair if for every possible input
(which typically consists of a candidate set, a vote set, a focus candidate,
and sometimes other parameters related to the nature of the attempted
alteration), either both or neither of the attempted attacks can be
successfully carried out [HHM20]. For each of the seven general (i.e., holding
for all election systems) electoral control type collapsing pairs found by
Hemaspaandra, Hemaspaandra, and Menton [HHM20] and for each of the additional
electoral control type collapsing pairs of Carleton et al. [CCH+ 22] for veto
and approval (and many other election systems in light of that paper's Theorems
3.6 and 3.9), both members of the collapsing pair have the same complexity
since as sets they are the same set. However, having the same complexity (as
sets) is not enough to guarantee that as search problems they have the same
complexity. In this paper, we explore the relationships between the search
versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra,
Hemaspaandra, and Menton [HHM20] and Carleton et al. [CCH+ 22], we prove that
the pair's members' search-version complexities are polynomially related (given
access, for cases when the winner problem itself is not in polynomial time, to
an oracle for the winner problem). Beyond that, we give efficient reductions
that from a solution to one compute a solution to the other. For the concrete
systems plurality, veto, and approval, we completely determine which of their
(due to our results) polynomially-related collapsing search-problem pairs are
polynomial-time computable and which are NP-hard.
