Greedy algorithm doesn't do that well in the worst case, even provided the odd cycle counting oracle.

Take large $n$, and consider complete bipartite $K_{n, n}$ with parts $V_0, V_1$ together with an additional disjoint triangle $T$, and connect all vertices of $T$ with two vertices $v, u \in V_0$ pairwise. Odd cycles in this graph consist of even paths in $K_{n, n}$ between $v$ and $u$ extended by an odd path in $T$ (either a single vertex or a Hamiltonian path), together with a single Hamiltonian cycle in $T$. One can see that:

• $v$ and $u$ are contained in all odd cycles except for one;
• vertices of $T$ and other vertices of $K_{n, n}$ are contained in fewer odd cycles.

A smallest OCT consists of two vertices of $T$, yet the greedy algorithm WLOG will first take $v$, and then will proceed to delete at least two other vertices (since the remaining graph contains $K_4$, namely, the union of $u$ and $T$).

Greedy algorithm doesn't do that well in the worst case, even provided the odd cycle counting oracle.

Take large $n$, and consider complete bipartite $K_{n, n}$ with parts $V_0, V_1$ together with an additional disjoint triangle $T$, and connect all vertices of $T$ with two vertices $v, u \in V_0$ pairwise. Odd cycles in this graph consist of paths in $K_{n, n}$ between $v$ and $u$ extended by a two-vertex path in $T$, together with $O(1)$ odd cycles confined to $\{v, u\} \cup T$. One can see that:

• $v$ and $u$ are contained in all odd cycles except for $O(1)$;
• vertices of $T$ and other vertices of $K_{n, n}$ are contained in at most $2 / 3 + o(1)$ fraction of all odd cycles.

A smallest OCT consists of two vertices of $T$, yet the greedy algorithm WLOG will first take $v$, and then will proceed to delete at least two other vertices (since the remaining graph contains $K_4$, namely, the union of $u$ and $T$).