Editing Bipartite graph (section)

===Odd cycle transversal===
{{main|Odd cycle transversal}}
[[File:Odd Cycle Transversal of size 2.png|thumb|A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.]]
[[Odd cycle transversal]] is an [[NP-complete]] [[algorithm]]ic problem that asks, given a graph ''G'' = (''V'',''E'') and a number ''k'', whether there exists a set of&nbsp;''k'' vertices whose removal from ''G'' would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
 | last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
 | contribution = Node-and edge-deletion NP-complete problems
 | doi = 10.1145/800133.804355
 | pages = 253–264
 | title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
 | year = 1978
 | title-link = Symposium on Theory of Computing | s2cid = 363248
| doi-access = free
 }}</ref> The problem is [[Parameterized complexity|fixed-parameter tractable]], meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of ''k''.<ref name=reed2004finding>{{citation
 | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
 | last2 = Smith | first2 = Kaleigh
 | last3 = Vetta | first3 = Adrian
 | doi = 10.1016/j.orl.2003.10.009
 | issue = 4
 | journal = Operations Research Letters
 | mr = 2057781
 | pages = 299–301
 | title = Finding odd cycle transversals
 | volume = 32
 | year = 2004| citeseerx = 10.1.1.112.6357
}}.</ref> The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd [[Cycle (graph theory)|cycles]].  Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle [[Transversal (combinatorics)|transversal]] set.  In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.

The ''edge bipartization'' problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also [[fixed-parameter tractable]], and can be solved in time <math display="inline">O\left(2^k m^2\right)</math>,<ref name=guo2006compression>{{citation
 | last1 = Guo | first1 = Jiong
 | last2 = Gramm | first2 = Jens
 | last3 = Hüffner | first3 = Falk
 | last4 = Niedermeier | first4 = Rolf
 | last5 = Wernicke | first5 = Sebastian
 | doi = 10.1016/j.jcss.2006.02.001
 | journal =  Journal of Computer and System Sciences
 | volume = 72
 | issue = 8
 | pages = 1386–1396
 | title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
 | year = 2006
| doi-access = free
 }}</ref> where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph.