Introduces the k-Tinhofer hierarchy between general graphs and Tinhofer graphs, gives algebraic and combinatorial characterizations, proves strict separations for each k, shows P-hardness of deciding membership in the next level, and proves FPT isomorphism testing for (n-k)-Tinhofer graphs.
The $k$-Dimensional Weisfeiler-Leman Algorithm
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this note, we provide details of the $k$-dimensional Weisfeiler-Leman Algorithm and its analysis from Immerman-Lander (1990). In particular, we present an optimized version of the algorithm that runs in time $O(n^{k+1}\log n)$, where $k$ is fixed (not varying with $n$).
fields
cs.CC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
Introduces the k-Tinhofer hierarchy between general graphs and Tinhofer graphs, gives algebraic and combinatorial characterizations, proves strict separations for each k, shows P-hardness of deciding membership in the next level, and proves FPT isomorphism testing for (n-k)-Tinhofer graphs.