Header menu link for other important links
X
Packing arc-disjoint cycles in bipartite tournaments
A.S. Jacob,
Published in Springer
2020
Volume: 12049 LNCS
   
Pages: 249 - 260
Abstract
An r-partite tournament is a directed graph obtained by assigning a unique orientation to each edge of a complete undirected r-partite simple graph. Given a bipartite tournament T on n vertices, we explore the parameterized complexity of the problem of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k. Although the maximization version of this problem can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in bipartite tournaments, surprisingly no algorithmic results seem to exist. We show that this problem can be solved in 2O(k log k)nO(1) time and admits a kernel with O(k2) vertices. © Springer Nature Switzerland AG 2020.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer
ISSN03029743
Open AccessNo