We present an O(mn) algorithm to determine whether a graph G
with m edges and n vertices has an odd cycle transversal of order
at most k, for any fixed k. We also obtain an algorithm that
determines, in the same time, whether a graph has a half integral packing of
odd cycles of weight k.