
Let G be an n-node bipartite tournament, i.e., a complete bipartite graph, each of whose edges has an orientation. We address the fixed-parameter complexity of the NP-complete problem of determining, for any given parameter k, whether G admits a k-node subset whose removal from G yields an acyclic graph. The best previously known upper bound, due to Sasatte, is $O(3^k\cdot \mbox{poly}(n))$ . In this paper, we show that the fixed-parameter complexity is $O(2^k\cdot\mbox{poly}(n))$ .
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
