Is there anything known about the following problem? Does it make sense at all? What is it called? Is it trivially equivalent to some other problem? What is the time-complexity?
Given an undirected (general/planar/bounded-degree/etc.) graph G=(V,E), find a maximum subset of edges E', such that G'=(V,E-E') is connected and for every edge e in E' there is an odd length cycle in G containing e, that contains no other edge in E'. (I consider simple cycles only, i.e. no vertex appears twice)
This seems similar to bipartization, but the results I have seen there are about the minimum number of vertices/edges needing to be removed, whereas I want the maximum number of edges that can be removed.
For example, the following graph:
* - * - * / \ * - * - * - * \ / * - * - *
We could cut one of the edges on the path in the middle, thus removing all odd cycles. However, we can do better by removing two edges, one in the top branch and one in the lower one.