We study possible winner problems related to uncovered set and Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study the following 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. Here we focus on two parameterizations of the problem: parameterized by ∣X∣ and parameterized by the number of arcs to be added to make all vertices of X be included in the uncovered set. In addition, we study a parameterized variant of the problem to decide whether we can make all vertices of X 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 O-indegree vertex. These parameterized problems are related to Banks set. For all these parameterized problems studied in this paper, we achieve XV results, W-hardness results as well as FPT results along with a kernelization lower bound.
展开▼
