Odd cycle transversal

A given ${\displaystyle n}$-vertex graph ${\displaystyle G}$ has an odd cycle transversal of size ${\displaystyle k}$, if and only if the Cartesian product of graphs ${\displaystyle G\square K_{2}}$ (a graph consisting of two copies of ${\displaystyle G}$, with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size ${\displaystyle n+k}$. The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it. In the other direction, a vertex cover of ${\displaystyle G\square K_{2}}$ 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). All such problems for nontrivial properties are NP-hard.[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 ${\displaystyle k}$. The development of these algorithms led to the method of iterative compression, a more general tool for many other parameterized algorithms.[1] The parameterized algorithms known for these problems take nearly-linear time for any fixed value of ${\displaystyle k}$.[4] Alternatively, with polynomial dependence on the graph size, the dependence on ${\displaystyle k}$ can be made as small as ${\displaystyle 2.3146^{k}}$.[5] In contrast, the analogous problem for directed graphs does not admit a fixed-parameter tractable algorithm under standard complexity-theoretic assumptions.[6]

• Maximum cut, equivalent to asking for a minimum set of edges whose removal leaves a bipartite graph