Possible winner problems on partial tournaments: a parameterized study

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve \(\mathcal {XP}\) results, \(\mathcal {W}\)-hardness results as well as \(\mathcal {FPT}\) results along with a kernelization lower bound for the problems studied in this paper.