4 papers · 1 filter
A Single Exponential-Time FPT Algorithm for Cactus Contraction
R. Krithika, Pranabendu Misra, Prafullkumar Tale
For a collection of graphs, the -\textsc{Contraction} problem takes a graph and an integer as input and decides if can be modified to some gr…
A Note on Arc-Disjoint Cycles in Bipartite Tournaments
Jasine Babu, Ajay Saju Jacob, R. Krithika +1
We show that for each non-negative integer k, every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7(k - 1).
The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments
R. Krithika, Abhishek Sahu, Saket Saurabh +1
Given a directed graph on vertices and a positive integer , the Arc-Disjoint Cycle Packing problem is to determine whether has arc-disjoint cycles. This problem…
Another Disjoint Compression Algorithm for OCT
R. Krithika, N. S. Narayanaswamy
We describe an elegant O*(2^k) algorithm for the disjoint compression problem for Odd Cycle Transversal based on a reduction to Above Guarantee Vertex Cover. We believe that this a…