14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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'? $\endgroup$ – domotorp May 14 '11 at 16:59
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.