Improved Parameterized Algorithms for Feedback Set Problems in Weighted Tournaments

Abstract

As our main result, we give an O((2.415)^kn^ω) algorithm for finding a feedback arc set of weight at most k in a tournament on n vertices with each vertex having weight at least 1. This improves the previously known bound of O(√k^kn^ωlogn) for the problem in unweighted tournaments. Here ω is the exponent of the best matrix multiplication algorithm. We also investigate the fixed parameter complexity of weighted feedback vertex set problem in a tournament. We show that (a) when the weights are restricted to positive integers, the problem can be solved as fast as the unweighted feedback vertex set problem, (b) if the weights are arbitrary positive reals then the problem is not fixed parameter tractable unless P=NP and (c) when the weights are restricted to be of at least 1, the problem can be solved in O((2.4143)^kn^ω) time.