Effective Computation of Immersion Obstructions for Unions of Graph Classes

摘要

In the final paper of the Graph Minors series [Neil RobertsoD and Paul D. Seymour. Graph minors XXIII. Nash-Williams' immersion conjecture J. Comb. Theory, Ser. B, 100(2):181-205, 2010.], N. Robertson and P. Seymour proved that graphs are well-quasi-ordered with respect to the immersion relation. A direct implication of this theorem is that each class of graphs that is closed under taking immersions can be fully characterized by forbidding a finite set of graphs (immersion obstruction set). However, as the proof of the well-quasi-ordering theorem is non-constructive, there is no generic procedure for computing such a set. Moreover, it remains an open issue to identify for which immersion-closed graph classes the computation of those sets can become effective. By adapting the tools that where introduced in [Isolde Adler, Martin Grohe and Stephan Kreutzer. Computing excluded minors, SODA, 2008: 641-650.] for the effective computation of obstruction sets for the minor relation, we expand the horizon of the computability of obstruction sets for immersion-closed graph classes. In particular, we prove that there exists an algorithm that, given the immersion obstruction sets of two graph classes that are closed under taking immersions, outputs the immersion obstruction set of their union.