Do the Odd Cycles of a Graph Define a Matroid?

Question

An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.

Question:

does the collection of "critical" sets of vertices, whose removal renders a graph bipartite, resemble a Matroid, i.e. will a greedy strategy yield a critical vertex set of minimal cardinality?

I am looking for a proof deciding the matroid property that either affirm the success of the greedy strategy or for a proof of at least the existence of instances, where the greedy strategy doesn't yield a minimal set of vertices whose removal renders the graph bipartite; a concrete counter example would be more than I dare to hope for in that case.

By a critical set of vertices, in this context, I mean a set of vertices whose removal renders a graph bipartite, but none of its proper subsets has that property.

By the greedy strategy I mean repeatedly removing a vertex that is on a maximal number of odd cycles in the graph resulting from previous greedy vertex deletions.

Please note that the question is not as to whether it is efficiently possible to determine the number of odd cycles on which a vertex; it is rather assumed that that information comes from a kind of oracle or whatever celestial being you prefer.

Answer 1

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$).