Abstract

The kk-dimensional Weisfeiler-Leman procedure (kk-WL), which colors kk-tuples of vertices in rounds based on the neighborhood structure in the graph, 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 kk-WL-equivalent if the kk-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the kk-WL-equivalence relation becomes finer as kk increases. We investigate to what extent standard graph parameters are preserved by kk-WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of kk-WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.