Packing Odd Circuits in Eulerian Graphs

Let C be the clutter of odd circuits of a signed graph (G,Σ). For nonnegative integral edge-weights w, we are interested in the linear program min(wtx: x(C)⩾1, for C∈C, and x⩾0), which we denote by (P). The problem of solving the related integer program clearly contains the maximum cut problem, which is NP-hard. Guenin proved that (P) has an optimal solution that is integral so long as (G,Σ) does not contain a minor isomorphic to odd-K5. We generalize this by showing that if (G,Σ) does not contain a minor isomorphic to odd-K5 then (P) has an integral optimal solution and its dual has a half-integral optimal solution.