On the Weisfeiler-Leman Dimension of Fractional Packing

The k-dimensional Weisfeiler-Leman procedure ([Formula: see text]) has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are [Formula: see text]-equivalent if dimention k does not suffice to distinguish them. [Formula: see text]-equivalence is known as fractional isomorphism of graphs, and the [Formula: see text]-equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by [Formula: see text]-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of [Formula: see text]-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.