zbMATH — the first resource for mathematics

Finding odd cycle transversals. (English) Zbl 1052.05061
Summary: 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\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
Full Text: DOI
[1] Karp, R., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[2] Reed, B., Mangoes and blueberries, Combinatorica, 19, 2, 267-296, (1999) · Zbl 0928.05059
[3] R. Rizzi, V. Bafna, S. Istrail, G. Lancia, Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem, Algorithms in Bioinformatics: Second International Workshop, Lecture Notes in Computer Science, Vol. 2452, Springer, Berlin, 2002, pp. 29-43. · Zbl 1016.68685
[4] Robertson, N.; Seymour, P., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 1, 65-110, (1995) · Zbl 0823.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.