Reducibility and flows on Feynman diagrams

A Feynman diagram of order n is a rooted mixed graph on 2n vertices consisting of a perfect matching of undirected edges (called V-lines) and a permutation formed by directed edges (call G-lines). A Feynman diagram is irreducible if and only if it is connected and cant be disconnected into two disjoint components by removing 2 Glines. Three algorithms to test the reducibility of Feynman diagrams were implemented and tested. The three algorithms are called quadratic, pseudolinear and randomized. Conservative flows are constructed in order to test for reducibility in all three algorithms. For a Feynman diagram with order n, the quadratic algorithm takes expected time O(n2). The pseudolinear algorithm takes expected time O(n) for orders up to 63, but takes expected time O(n2) for arbitrarily higher orders. The randomized algorithm takes expected time O(n log n) for diagrams of any order, but is effectively linear for n 215. Testing was done on Feynman diagrams of various orders. Timing results are reported and analyzed. For order less than 23, the quadratic and pseudolinear algorithms run faster than the randomized algorithm because of the overhead of checking false cut-pairs in the latter approach. For larger n, the randomized algorithm becomes much faster than the other two. The pseudolinear algorithm runs faster than the quadratic algorithm due to its smaller constant factor, even for higher order diagrams.