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: | Marx Dniel, Guillemot Sylvain |
Keywords: | optimization, combinatorial optimization |
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.