Possible Winner Problems on Partial Tournaments: A Parameterized Study

摘要

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 0-indegree vertex. These parameterized problems are related to Banks set. For all these parameterized problems studied in this paper, we achieve XP results, W-hardness results as well as FPT results along with a kernelization lower bound.