A weak immersion relation on graphs and its applications (Q5931419)

A graph \(H\) is said to be weakly immersed in a graph \(G\) if \(H\) can be obtained from \(G\) by a sequence of the following three operations: taking a subgraph, splitting a vertex, and lifting a pair of adjacent edges. The weak immersion relation has the useful property that finite graphs are well-quasi-ordered by it, which also holds for graphs with some vertices designated as terminals. As a result, any family of finite graphs that is closed under weak immersion can be characterized by a finite number of minimal forbidden graphs called obstructions. Weak immersion offers two advantages over immersions for practical applications. First, although closure under weak immersion implies closure under immersion, families can have significantly fewer obstructions under weak immersion. Hence weak immersion can provide simpler characterizations for closed families. Second, for every fixed graph \(H\), there is a polynomial-time algorithm to decide whether \(H\) is weakly immersed in an input graph \(G\). Consequently, there is a polynomial-time membership test for any family that is closed under weak immersion. In principle, testing for weak immersion is as fast as testing for immersion. Thus the simpler characterization provided by weak immersion may lead to faster membership algorithms.