<p>An upper bound on $|E&#39;|$ is the sum of the cycle ranks of the non-bipartite 2-vertex-connected components, since the cycles for the edges in $E&#39;$ are necessarily linearly independent. But I think this is not tight: the 3-sun (a six-vertex maximal outerplanar graph formed from a 6-cycle by connecting three of its vertices in a triangle) has cycle rank four but the maximum size of $E&#39;$ appears to be three.</p>

CC BY-SA 3.0
2011-05-15T07:21:35.530Z
2011-05-15T07:21:35.530Z
David Eppstein
<p>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?</p>

<p>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)</p>

<p>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.</p>

<p>For example, the following graph:</p>

<pre><code>  * - * - * 
 /         \
* - * - * - *
 \         /
  * - * - *
</code></pre>

<p>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. </p>

CC BY-SA 3.0
2011-05-14T16:59:07.113Z
A related question - if we have an edge set E' and another edge e, can we decide fast whether every odd cycle containing e avoids E'?
domotorp
<ds.algorithms><graph-theory>
Hitting odd cycles
László Kozma
# Hitting odd cycles

(Asked by: username_0 on 2011-05-14)

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.

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: A related question - if we have an edge set E' and another edge e, can we decide fast whether every odd cycle containing e avoids E'?  

---

## 1 answers

### Answer by username_2 on 2011-05-15. Score: 7

An upper bound on $|E'|$ is the sum of the cycle ranks of the non-bipartite 2-vertex-connected components, since the cycles for the edges in $E'$ are necessarily linearly independent. But I think this is not tight: the 3-sun (a six-vertex maximal outerplanar graph formed from a 6-cycle by connecting three of its vertices in a triangle) has cycle rank four but the maximum size of $E'$ appears to be three.


---

