Odd cycle transversal

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.[1]

A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.

Relation to vertex cover

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]

Algorithms and complexity

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]

See also

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

References

1. Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parameterized Algorithms, Springer, pp. 64–65, doi:10.1007/978-3-319-21275-3, ISBN 978-3-319-21274-6, MR 3380745
2. Garey, Michael R.; Johnson, David S. (1979), "GT21: Induced subgraph with property Π", Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, p. 195
3. 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
4. Kawarabayashi, Ken-ichi; Reed, Bruce (2010), "An (almost) linear time algorithm for odd cycles transversal", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 365–378, CiteSeerX 10.1.1.215.2581, doi:10.1137/1.9781611973075.31, ISBN 978-0-89871-701-3, MR 2809682
5. Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket (2014), "Faster parameterized algorithms using linear programming", ACM Transactions on Algorithms, 11 (2): Art. 15, 31, arXiv:1203.0833, doi:10.1145/2566616, MR 3283570
6. Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket; Zehavi, Meirav (2017), Parameterized complexity and approximability of directed odd cycle transversal, arXiv:1704.04249, Bibcode:2017arXiv170404249L