Are there poly time algorithms to determine if a graph is almost bipartite?
The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See:

Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355.

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, doi:10.1016/j.orl.2003.10.009.

Hüffner, Falk (2005), "Algorithm engineering for optimal graph bipartization", Experimental and Efficient Algorithms: 240–252, doi:10.1007/11427186_22.

The edge version has been called "edge bipartization"; it's also NP-complete but fixed-parameter tractable. See:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", JCSS 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001.

(added following daniello's comment):

Odd cycle transversal has an $O(\sqrt{\log n})$ approximation algorithm, but (assuming the Unique Games Conjecture) no constant-factor approximation; see (references copied from "On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal" by Jansen and Kratsch):

Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems, STOC'05, pp. 573–581.

Khot, S., On the power of unique 2-prover 1-round games, STOC '02, pp. 767–775.

Wernicke, S., On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Master’s thesis, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)