Faster separation of 1-wheel inequalities by graph products

Using graph products we present an O(|V|2|E|+|V|3log|V|)O(|V|2|E|+|V|3log|V|) separation algorithm for the nonsimple 11-wheel inequalities by Cheng and Cunningham (1997) of the stable set polytope, which is faster than their O(|V|4)O(|V|4) algorithm.There are two ingredients for our algorithm. The main improvement stems from a reduction of the separation problem to multiple shortest path problems in an auxiliary graph having only 6|V|6|V| vertices and 9|E|9|E| arcs, thereby preserving low sparsity. Then Johnson’s algorithm can be applied to the auxiliary graph of same sparsity as the original one.In contrast, Cheng and Cunningham’s auxiliary graph is by construction dense, |E|=O(|V|2)|E|=O(|V|2), so application of Johnson’s algorithm provides no large improvement.