Computational Aspects of Covering in Dominance Graphs∗

Various problems in AI and multiagent systems can be tack-led by finding the “most desirable ” elements of a set given some binary relation. Examples can be found in areas as di-verse as voting theory, game theory, and argumentation the-ory. Some particularly attractive solution sets are defined in terms of a covering relation—a transitive subrelation of the original relation. We consider three different types of cov-ering (upward, downward, and bidirectional) and the corre-sponding solution concepts known as the uncovered set and the minimal covering set. We present the first polynomial-time algorithm for finding the minimal bidirectional covering set (an acknowledged open problem) and prove that decid-ing whether an alternative is in a minimal upward or down-ward covering set is NP-hard. Furthermore, we obtain various set-theoretical inclusions, which reveal a strong connection between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other hand. In particular, we show that every stable set is also a minimal upward covering set