an (almost) linear time algorithm for odd cycles transversal
We consider the following problem, which is called the odd cycles transversal problem . Input: A graph G and an integer k . Output: A vertex set X ? V(G) with | X | ? k such that G -- X is bipartite. We present an O(m?(m, n )) time algorithm for this problem for any fixed k , where n, m are the number of vertices and the number of edges, respectively, and the function ?( m, n ) is the inverse of the Ackermann function (see by Tarjan [38]). This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(nm ) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X ' ? E(G ) such that G -- X ' is bipartite. Using this algorithm and the recent result in [16], we give an O(m?(m, n ) + n log n ) algorithm for the following problem for any fixed k: Input: A graph G and an integer k . Output: Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C 1 ,..., C k in G such that each vertex is on at most two of these odd cycles. This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(n 3 ) time algorithm for this problem. We also give a much simpler and much shorter proof for the following result by Reed [28]. The Erd&odblac;s-Psa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f (k ) such that G -- X is bipartite for some function f of k . Note that the Erd&odblac;s-Psa property does not hold for odd cycles in general.
nearly linear time algorithm erd&odblac s-p&oacute sa property