A submodular measure and approximate Gomory–Hu theorem for packing odd trails

This paper, published after I left academia, explores the "perimeter" measure that plays a key role in my doctoral research. It is mostly based on Chapter 4 of my PhD thesis.

A submodular measure and approximate Gomory-Hu theorem for packing odd trails. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Ross Churchley and Bojan Mohar (2018). Motivated by a problem about totally odd immersions of graphs, we define the odd edge-connectivity$\lambda_o(u, v)$ as the maximum number of edge-disjoint trails of odd length from $u$ to $v$. It was recently discovered that $\lambda_o(u, v)$ can be approximated up to a constant multiplicative factor using the usual edge-connectivity between $u$ and $v$ and the minimum value of another parameter that measures "how far from a bipartite graph" the part of the graph around $u$ and $v$ is.

In this paper, we formalize this second ingredient and call it the perimeter. We prove that perimeter is a submodular function on the vertex-sets of a graph. Using this fact, we obtain a version of the Gomory–Hu Theorem in which minimum edge-cuts are replaced by sets of minimum perimeter. We construct (in polynomial time) a rooted forest structure, analogous to the Gomory–Hu tree of a graph, which encodes a collection of minimum-perimeter vertex-sets. Although the classical Gomory–Hu Theorem extends to arbitrary symmetric submodular functions, our result is novel and indicates a possibility for further generalizations.

These results have significant implications for the study of path and trail systems with parity constraints. We present two such applications: an efficient data structure for storing approximate odd edge-connectivities for all pairs of vertices in a graph, and a rough structure theorem for graphs with no "totally odd" immersion of a large complete graph.

Odd disjoint trails and totally odd graph immersions

I have succesfully defended my PhD thesis! It's "packed" with results on graph immersions with parity restrictions, and "covers" odd edge-connectivity, totally odd clique immersions, and a new submodular measure that's intimately connected with both.