  We study the complexity of the destructive bribery problem---an external
agent tries to prevent a disliked candidate from winning by bribery
actions---in voting over combinatorial domains, where the set of candidates is
the Cartesian product of several issues. This problem is related to the concept
of the margin of victory of an election which constitutes a measure of
robustness of the election outcome and plays an important role in the context
of electronic voting. In our setting, voters have conditional preferences over
assignments to these issues, modelled by CP-nets. We settle the complexity of
all combinations of this problem based on distinctions of four voting rules,
five cost schemes, three bribery actions, weighted and unweighted voters, as
well as the negative and the non-negative scenario. We show that almost all of
these cases are NP-complete or NP-hard for weighted votes while approximately
half of the cases can be solved in polynomial time for unweighted votes.
