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.

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.

List-monopolar partitions of claw-free graphs

The list monopolar partition problem asks whether a graph G together with lists L(v) ⊆ {0, 1}, v ∈ V(G) admits a mapping f: V(G) → {0, 1} such that f(v) ∈ L(v) for each source induces an independent set and f−1(1) induces a disjoint union of cliques in G. This problem is NP-complete in general. We show that the problem is solvable in time O(n2m) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.

List-monopolar partitions of claw-free graphs. Ross Churchley and Jing Huang. Discrete Mathematics 312 (17), 2545–2549. September 2012.

Line-polar graphs: characterization and recognition

A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P3-free subgraph (i.e., a matching) and B induces a P4-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) time algorithm to solve the stated recognition problem.

Line-polar graphs: characterization and recognition. Ross Churchley and Jing Huang. SIAM Journal on Discrete Mathematics 25 (3), 1269–1284. August 2011.