TY - GEN
T1 - Weisfeiler-lehman refinement requires at least a linear number of iterations
AU - Fürer, Martin
PY - 2001
Y1 - 2001
N2 - Let Lk,m be the set of formulas of first order logic containing only variables from x1, x2, ... xk and having quantifier depth at most m. Let Ck,m be the extension of L k,m obtained by allowing counting quantifiers meaning that there are at least i distinct xj 's. It is shown that for constants h ≥ 1, there are pairs of graphs such that h-dimensional Weisfeiler-Lehman refinement (h-dim W-L) can distinguish the two graphs, but requires at least a linear number of iterations. Despite of this slow progress, 2h-dim W-L only requires O(n) iterations, and 3h-1-dim W-L only requires O(log n) iterations. In terms of logic, this means that there is a c > 0 and a class of non-isomorphic pairs (GhnHhn) of graphs with G hn and Hhn having O(n) vertices such that the same sentences of Lh+1cn and Ch+1cn hold (h + 1 variables, depth cn), even though Ghn and H hn can already be distinguished by a sentence of L k,m and thus Ckm for some k > h and m = O(log n).
AB - Let Lk,m be the set of formulas of first order logic containing only variables from x1, x2, ... xk and having quantifier depth at most m. Let Ck,m be the extension of L k,m obtained by allowing counting quantifiers meaning that there are at least i distinct xj 's. It is shown that for constants h ≥ 1, there are pairs of graphs such that h-dimensional Weisfeiler-Lehman refinement (h-dim W-L) can distinguish the two graphs, but requires at least a linear number of iterations. Despite of this slow progress, 2h-dim W-L only requires O(n) iterations, and 3h-1-dim W-L only requires O(log n) iterations. In terms of logic, this means that there is a c > 0 and a class of non-isomorphic pairs (GhnHhn) of graphs with G hn and Hhn having O(n) vertices such that the same sentences of Lh+1cn and Ch+1cn hold (h + 1 variables, depth cn), even though Ghn and H hn can already be distinguished by a sentence of L k,m and thus Ckm for some k > h and m = O(log n).
UR - http://www.scopus.com/inward/record.url?scp=77956227541&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956227541&partnerID=8YFLogxK
U2 - 10.1007/3-540-48224-5_27
DO - 10.1007/3-540-48224-5_27
M3 - Conference contribution
AN - SCOPUS:77956227541
SN - 3540422870
SN - 9783540422877
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 322
EP - 333
BT - Automata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
A2 - Orejas, Fernando
A2 - Spirakis, Paul G.
A2 - van Leeuwen, Jan
PB - Springer Verlag
T2 - 28th International Colloquium on Automata, Languages and Programming, ICALP 2001
Y2 - 8 July 2001 through 12 July 2001
ER -