A faster FPT algorithm for Bipartite Contraction

A faster FPT algorithm for Bipartite Contraction

0.00 Avg rating0 Votes
Article ID: iaor20141108
Volume: 113
Issue: 22-24
Start Page Number: 906
End Page Number: 912
Publication Date: Nov 2013
Journal: Information Processing Letters
Authors: ,
Keywords: optimization, combinatorial optimization
Abstract:

The Bipartite Contraction problem is to decide, given a graph G and a parameter k, whether we can obtain a bipartite graph from G by at most k edge contractions. The fixed-parameter tractability of the problem was shown by Heggernes et al. [13], with an algorithm whose running time has double-exponential dependence on k. We present a new randomized FPT algorithm for the problem, which is both conceptually simpler and achieves an improved 2ˆOˆ(ˆkˆˆˆ2ˆ)nm running time, i.e., avoiding the double-exponential dependence on k. The algorithm can be derandomized using standard techniques.

Reviews

Required fields are marked *. Your email address will not be published.