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

Motivated by a problem about totally odd immersions of graphs, we define the odd edge-connectivity λo(u, v) as the maximum number of edge-disjoint trails of odd length from u to υ. It was recently discovered that λ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.

A submodular measure and approximate Gomory-Hu theorem for packing odd trails. Ross Churchley and Bojan Mohar. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 210–218. January 2018.

Odd disjoint trails and totally odd graph immersions

The odd edge-connectivity between two vertices in a graph is the maximum number λo(u, v) of edge-disjoint (u, v)-trails of odd length. In this thesis, we define the perimeter of a vertex-set, a natural upper bound for the odd edge-connectivity between some of its constituent pairs. Our central result is an approximate characterization of odd edge-connectivity: λo(u, v) is bounded above and below by constant factors of the usual edge-connectivity λ(u, v) and/or the minimum perimeter among vertex-sets containing u and v.

The relationship between odd edge-connectivity and perimeter has many implications, most notably a loose packing–covering duality for odd trails. (In contrast, odd paths do not obey any such duality.) For Eulerian graphs, we obtain a second, independent proof of the packing–covering duality with a significantly better constant factor. Both proofs can be implemented as polynomial-time approximation algorithms for λo(u, v). After observing that perimeter satisfies a submodular inequality, we are able to prove an analogue of the Gomory–Hu Theorem for sets of minimum perimeter and, consequently, to construct an efficient data structure for storing approximate odd edge-connectivities for all vertex pairs in a graph.

The last part of the thesis studies more complicated systems of odd trails. A totally odd immersion of a graph H in another graph G is a representation in which vertices in H correspond to vertices in G and edges in H correspond to edge-disjoint odd trails in G. Using our perimeter version of the Gomory–Hu Theorem, we describe the rough structure of graphs with no totally odd immersion of the complete graph Kt. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.

Odd disjoint trails and totally odd graph immersions. Ross Churchley. PhD thesis, Simon Fraser University. January 2017. (Senior supervisor: Bojan Mohar)

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.

On the polarity and monopolarity of graphs

Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle-free graphs and claw-free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP-complete for triangle-free graphs. We also show that for claw-free graphs the former is NP-complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP-completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw-free graphs uses a subroutine similar to the well-known breadth-first search algorithm and is based on a new structural characterization of monopolar claw-free graphs, a generalization of one for monopolar line graphs obtained earlier.

On the polarity and monopolarity of graphs. Ross Churchley and Jing Huang. Journal of Graph Theory 76 (2), 138–148. June 2014.

Solving partition problems with colour-bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.

Solving partition problems with colour-bipartitions. Ross Churchley and Jing Huang. Graphs and Combinatorics 30 (2), 353–364. March 2014.

On graph-transverse matchings

Given graphs G, H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently.

The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.

On graph-transverse matchings. Ross Churchley. MSc thesis, University of Victoria. August 2012. (Senior supervisor: Jing Huang)

Complexity of cycle-transverse matching problems

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of H in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each Cl with l ≥ 3 is NP-complete. In this paper, we study an edge version of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of H. We show that the problem for C3 is polynomial and for each Cl with l ≥ 4 is NP-complete. Our results imply that the stable transversal problem for each Cl with l ≥ 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C3, when restricted to line graphs, is polynomial.

Complexity of cycle-transverse matching problems. Ross Churchley, Jing Huang, and Xuding Zhu. Lecture Notes in Computer Science 7056, 135–143. 2011.