The Graph Minor Algorithm with Parity Conditions

We generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity version. We give polynomial time algorithms for the following problems: 1) the parity H-minor (Odd K_k -minor) containment problem, and 2) the disjoint paths problem with k terminals and the parity condition for each path, as well as several other related problems. We present an O(ma(m, n)n) time algorithm for these problems for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function a(m,n) is the inverse of the Ackermann function (see Tarjan [69]). Note that the first problem includes the problem of testing whether or not a given graph contains k disjoint odd cycles (which was recently solved in [24], [34]), if we fix H to be equal to the graph of k disjoint triangles. The algorithm for the second problem generalizes the Robertson Seymour algorithm for the k-disjoint paths problem. As with the Robertson-Seymour algorithm for the k-disjoint paths problem for any fixed k, in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor. We emphasize that our proof for the correctness of the above algorithms does not depend on the full power of the Graph Minor structure theorem [56]. Although the original Graph Minor algorithm of Robertson and Seymour does depend on it and our proof does have similarities to their arguments, we can avoid the structure theorem by building on the shorter proof for the correctness of the graph minor algorithm in [35]. This work was done as a part of an INRIA-NII collaboration under MOU grant, and partially supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas "New Horizons in- Computing" Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, by C & C Foundation, by Kayamori Foundation and by Inoue Research Award for Young Scientists. Consequently, we are able to avoid the much of the heavy machinery of the Graph Minor structure theory. Utilizing some results of [35] and [62], [63], our proof is less than 50 pages.