On dual version of Weisfeiler – Lehman algorithm

Анотація

We study a simplified variant of the Weisfeiler – Lehman graph canonization algorithm that corresponds to the fragment of the first order logic with bounded number of variables precisely in the same way as the standard variant corresponds to this fragment, enriched with counting quantifiers. We propose a natural dual version of the color refinement subroutine and prove that the dual algorithm has optimum dimension by one exceeding that of the standard algorithm.

Розглянуто спрощений варіант алгоритму канонізації графів Вайсфайлера – Лемана, який відповідає фрагментові логіки першого порядку з обмеженою кількістю змінних таким же чином, як стандартний варіант відповідає цьому фрагменто­ві, збагаченому рахуючими кванторами. Запропоновано природну дуальну версію процедури подрібнення кольорів і доведено, що оптимальна розмірність дуального алгоритму на одиницю перевищує оптимальну розмірність стандартного алго­ритму.