Weak duality for packing edge-disjoint odd trails

This paper, coauthored with my supervisor Bojan Mohar and colleague Hehui Wu, was the first entry in my doctoral research into graph immersions with parity restrictions.

Despite Menger's famous duality between packings and coverings of (u,v)(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)(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)\nu(u, v) denotes the maximum number of edge-disjoint (u,v)(u, v)-trails of odd length in a graph GG and τ(u,v)\tau(u, v) denotes the minimum number of edges that intersect every such trail, then

ν(u,v)τ(u,v)8ν(u,v)\nu(u,v) \leq \tau(u, v) \leq 8\nu(u,v)

The proof leads to a polynomial-time algorithm to find, for any given kk, either kk edge-disjoint odd (u,v)(u, v)-trails or a set of fewer than 8k8k edges intersecting all odd (u,v)(u, v)-trails. This yields a constant factor approximation algorithm for the packing number ν(u,v)\nu(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.

Ross Churchley, Bojan Mohar, and Hehui Wu[1]

I am grateful to NSERC for supporting this research through an Alexander Graham Bell Canada Graduate Scholarship.


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