Computational aspects of covering in dominance graphs

Various problems in AI and multiagent systems can be tackled by finding the "most desirable" elements of a set given some binary relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. 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 covering (upward, downward, and bidirectional) and the corresponding 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 deciding whether an alternative is in a minimal upward or downward 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.