Odd cycle transversal

Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

, with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size

can be transformed into an odd cycle transversal by keeping only the vertices for which both copies are in the cover.

The vertices outside of the resulting transversal can be bipartitioned according to which copy of the vertex was used in the cover.

[1] The problem of finding the smallest odd cycle transversal, or equivalently the largest bipartite induced subgraph, is also called odd cycle transversal, and abbreviated as OCT.

It is NP-hard, as a special case of the problem of finding the largest induced subgraph with a hereditary property (as the property of being bipartite is hereditary).

[2][3] The equivalence between the odd cycle transversal and vertex cover problems has been used to develop fixed-parameter tractable algorithms for odd cycle transversal, 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

[1] The parameterized algorithms known for these problems take nearly-linear time for any fixed value of

[5] In contrast, the analogous problem for directed graphs does not admit a fixed-parameter tractable algorithm under standard complexity-theoretic assumptions.