Weak duality for packing edge-disjoint odd trails

Despite Menger’s famous duality between packings and coverings of (u, v)-paths in a graph, there is no duality when we require the paths be odd: a graph with no two edge-disjoint odd (u, v)-paths may need an arbitrarily large number of edges to cover all such paths. In this paper, we study the relaxed problem of packing odd trails. Our main result is an approximate duality for odd trails: if ν(u, v) denotes the maximum number of edge-disjoint (u, v)-trails of odd length in a graph G and τ(u, v) denotes the minimum number of edges that intersect every such trail, then ν(u, v) ≤ τ(u, v) ≤ ν(u, v). The proof leads to a polynomial-time algorithm to find, for any given k, either k edge-disjoint odd (u, v)-trails or a set of fewer than 8k edges intersecting all odd (u, v)-trails. This yields a constant factor approximation algorithm for the packing number ν(u, v).

This result generalizes to the setting of signed graphs and to the setting of group-labelled graphs, in which case “odd length” is replaced by “non-unit product of labels”. The motivation for this result comes from the study of totally odd graph immersions, and our results explain, in particular, why there is an essential difference between the totally odd weak and strong immersions.

Weak duality for packing edge-disjoint odd (u, v)-trails. Ross Churchley, Bojan Mohar, and Hehui Wu. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 2086–2094. January 2016.