| Article ID: | iaor20141086 |
| Volume: | 113 |
| Issue: | 22-24 |
| Start Page Number: | 849 |
| End Page Number: | 851 |
| Publication Date: | Nov 2013 |
| Journal: | Information Processing Letters |
| Authors: | Krithika R, Narayanaswamy N S |
| Keywords: | graphs |
Given a graph G and an odd cycle transversal T, we describe an elegant Oˆ(2ˆ|ˆTˆ|) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe that our algorithm, based on a reduction to Vertex Cover, is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between Odd Cycle Transversal and Vertex Cover.